CSE News and Announcements

Dec 21, 2001
EECS 598-02 Randomized Computation    Bookmark and Share
Winter 2002

Instructor: Satyanarayana V. Lokam (satyalv@eecs.umich.edu)

Time and Place: Tue and Thu 11:30 AM -- 1:30 PM, 3433 EECS.

Credit Hours: 4 CSE students can take this course for 500+ level credit.

Prerequisites: A basic course in algorithms or computational complexity and familiarity with elementary algebra and probability theory.

Description: For several important problems, use of randomness yields the most efficient algorithms known, or the simplest, or both. In fact, randomness is essential for certain tasks in cryptography and distributed computation. As a result, research in randomized algorithms has seen a phenomenal growth in recent years. In the first half of this course, we will study a collection of techniques for effectively using randomization and for analyzing randomized algorithms. We will pick examples from a variety of settings and problem areas.

Given that randomization helps, where do computers get their randomness from? In practice, we often use Pseudo-Random Generators (PRG's). But, when is the output of a PRG ``random enough" to replace a source of pure random bits? How do we construct such good PRG's? Even assuming computers do have access to ``pure randomness," how dramatic a speedup can we achieve using randomness? In the second half of the course, we will study recent results that address such issues. Important results in this area have rigorously established the intimate relations among the notions of randomness, computation,and information.

Attempts to understand some basic scientific questions, use of simple, but elegant, mathematics, and building rigorous foundations for important practical applications are some of the interesting highlights of this course.

Main Topics:

  • Background from Probability Theory
  • Randomized Algorithms
  • Derandomization
  • Pseudo-Random Generators
Grading: Homework and term papers/final projects.

Homework: 50%
Term Paper/Final Project: 50%

For more up-to-date information, please visit: http://www.eecs.umich.edu/~satyalv/rand/
 
EECS News by Topic
EECS News by Faculty Name
CSE in the News 
04/17/14 Scientific American: Heartbleed Software Snafu: The Good, the Bad and the Ugly
04/17/14 New York Times: Study Finds No Evidence of Heartbleed Attacks Before the Bug Was E...
04/15/14 Michigan Daily: Internet security flaw left University sites vulnerable
04/15/14 ARS Technica: Researchers find thousands of potential targets for Heartbleed OpenS...
04/15/14 Bloomberg: Hacker From China Wastes Little Time in Exploiting Heartbleed
04/15/14 Bloomberg: Heartbleed Hackers Steal Encryption Keys in Threat Test

CSE Research News 
04/17/14 Halderman and Lafortune Join TerraSwarm Research Center
04/07/14 Michael Lewis says the market is rigged. But his Flash Boys rigged themselves.
04/01/14 Researchers Win Best Paper Award at ISPASS 2014
04/01/14 Technological Singularity Passes, Unnoticed Until Now
03/05/14 Michael Wellman Recognized with ACM/SIGAI Autonomous Agents Research Award
02/21/14 New Center Develops Technologies to Help Youths with Disabilities

CSE News 
03/26/14 CSE Connects at SXSW 2014
03/24/14 Prospective Grad Students Visit, Learn About CSE
03/13/14 CSE Connects at Tapia Celebration of Diversity in Computing
02/03/14 Karem Sakallah Continues Commitment to Qatar Computing Research Institute
01/30/14 State Farm Gift Supports Student Projects Lab
01/23/14 Career Center Report Shows Computer Scientists Highly Sought, Best Compensated

CSE Faculty and Staff Awards 
04/03/14 Noble and Wilson Named as Learning Analytics Fellows
03/26/14 Kevin Fu Selected for World Economic Forum Young Scientist Award
02/25/14 Narayanasamy and Olson Named Morris Wellman Faculty Development Professors
02/07/14 Daniel Atkins Elected to National Academy of Engineering
01/24/14 2014 EECS Outstanding Achievement Awards
01/23/14 Four CSE Faculty Selected for College of Engineering Awards

CSE Student News and Awards 
04/18/14 Jill Bender Chosen for CoE Distinguished Leadership Award
04/16/14 SWE Hosts G.R.E.A.T. Day for Girls
04/11/14 Hands-On Robotics (video)
04/08/14 Forest Agostinelli Selected for NSF Graduate Research Fellowship
04/08/14 Branden Ghena Selected for NSF Graduate Research Fellowship
04/08/14 Elizabeth Mamantov Selected for NSF Graduate Research Fellowship

CSE Alumni News 
03/07/14 Alumni Spotlight-Dawson Yee: Kinect-ing Xbox to the World
03/03/14 CSE Alum Dongyoon Lee Selected for ProQuest Dissertation Award
12/20/13 Hector J. Garcia Selected for Bouchet Graduate Honor Society
11/12/13 CSE Alumna Mona Attariyan Selected for Ritchie Disseration Award
07/23/13 Tony Fadell: From Apple to Nest Labs, Always a Designer
06/26/13 Computer Engineering Alum Marius Eriksen Featured in Wired

CSE Course Announcements 
04/09/14 Fall 2014: Hands-On Robotics
04/03/14 Fall 2014: EECS 598-002 Power Semiconductor Devices
04/03/14 Fall 2014: EECS 598-001 Analysis of Electric Power Distribution Systems and Loads
03/20/14 Fall 2014: Applied matrix algorithms for signal processing, data analysis and mach...
11/26/13 Winter 2014: EECS 498-003 Multidisciplinary Capstone (MDE) Design Pilot
11/06/13 Winter 2014: EECS 598-007 Infrastructure for Vehicle Electrification

Add News Item     Update News Items