Computers can now drive cars and find cancer in x-rays. For better or worse, this will change the world (and the job market). Strangely designing these algorithms is not done by telling the computer what to do or even by understanding what the computer does. The computers learn themselves from lots and lots of data and lots of trial and error. This learning process is more analogous to how brains evolved over billions of years of learning. The machine itself is a neural network which models both the brain and silicon and-or-not circuits, both of which are great for computing. The only difference with neural networks is that what they compute is determined by weights and small changes in these weights give you small changes in the result of the computation. The process for finding an optimal setting of these weights is analogous to finding the bottom of a valley. "Gradient Decent" achieves this by using the local slope of the hill (derivatives) to direct the travel down the hill, i.e. small changes to the weights. There is some theory. If a machine is found that gives the correct answers on the randomly chosen training data without simply memorizing, then we can prove that with high probability this same machine will also work well on never seen before instances.

Second level of Machine Learning (These topics are likely 30 min each)
- Generalizing from Training Data: We can prove that if we successfully train on enough randomly choose training data, then the produced machine generalities well to random examples never seen before.
- Reinforcement Learning & Markoff Chains: The basic theory needed to learn to solve some complex multi-step task.
- Dimension Reduction & Maximum Likelihood: How to compress your data while retaining the key features.
- Convolutional & Recurrent Networks: Used for learning images and sound that are invariant over location and time.
- Generative Adversarial Networks: Used for understanding and producing a random data item.
- Back Propagation: We could learn how to use matrix multiplication to learn the slope to your error space.
- Bayesian Inference: Given the probability of a symptom given a disease, we can compute the probability of a disease given a symptom.
- Decision Trees & Clustering: The basics.

Scheduling Problems

Most broadly, this area of research considers the scheduling to a steady stream of incoming jobs, a shared resource such as processing time, battery power, or internet bandwidth. The problem is to determine how to best allocate and reallocate these resources to the jobs as they arrive and complete in a way that minimizes some global quality of service measure. One difficulty is the lack of knowledge that the scheduler has. The scheduler is said to be on-line if it does not know what jobs are going to arrive in the future, non-clairvoyant if it does not know the properties of the jobs currently in the system, and distributed if decisions are not made centrally. A second difficulty is that even with this information, most variants of the problem are NP-complete. The problem is to find in real time a schedule that is almost as good as the optimal schedule when you do not have complete information. We provide some answers to this question using the resource augmentation competitive analysis framework. This involves proving that given any input sequence, the algorithm, when given a constant times more of resource, performs within a constant times the efficiency as the all knowing all powerful optimal algorithm.

Varying Degrees of Parallelizability: As chips with hundreds to thousand of processors chips dominate the market in the next decade, it is generally agreed that developing software to harness their power is going to be a much more difficult technical challenge than the development of the hardware. Suppose you must allocated your processors to incoming jobs in the way that minimizes the average completion time of the jobs. Suppose that some of these jobs are parallelizable and hence can effectively unitize any processors that you give it. Others are sequential, so giving it extra processors is a wa0ste. We prove if you have twice as many processors as God, you can do almost as well as him simply by spreading your processors evenly among the jobs that are alive. This result was considered break through in this area, because no one previously believed that it could possibly be true. Ten years later it became a chapter in "The Encyclopedia of Algorithms." We also give a more complex algorithm that only needs 1+eps times as many processors.

Power Management: ``What matters most to the computer designers at Google is not speed, but power, low power, because data centers can consume as much electricity as a city.'' --- Dr. Eric Schmidt, CEO of Google. The most commonly used power management technique is speed scaling, which involves changing the speed of each processor. In tandem to determining at each time, which job to run on each processor, the operating system will need a speed scaling policy for setting the speed of each processor. We consider developing operating system algorithms/policies for scheduling processes with varying degrees of parallelism in a multiprocessor setting in a way that both optimizes some schedule quality of service objective, as well as some power related objective.

Broadcast Scheduling: We investigate server scheduling policies to minimize average user perceived latency in systems where multiple clients request data from a server and these are returned on a broadcast channel. Possibly being able to satisfy many requests to a common file with a single broadcast, allows the system to be more scalable to large numbers of clients. One notable commercial example is movies-on-demand. We provide new on-line scheduling algorithms and new analysis techniques.

TCP: The standard for reliable communication on the Internet is the well-known Transport Control Protocol (TCP). It performs well both in practice and extensive simulation have been done, but there have been minimal theoretical results. We evaluate the performance of TCP using the traditional competitive analysis framework, comparing its performance with that of an optimal offline algorithm.
* Warning: I do not do TCP AT ALL. I am a theory person. I prove theorems.