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 multistep 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.
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 moviesondemand. We provide new online scheduling algorithms and new analysis techniques.
TCP:
The standard for reliable communication on the Internet is the
wellknown 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.
Braching Programs:
The most powerful model of computation measuring the
amount of space used by an algorithm is branching programs. It is
represented by a directed acyclic graph of states. At each point in
time, the computation is in a particular state. Imagine that the name
of this state specifies everything the computation knows. For example,
being in state q
Communication Complexity: Suppose Alice knows some information x and Bob knows y and together they want to solve some task f(x,y). Communication complexity measures the number of bits they must communicate in order to achieve this. Shannon's entropy is a good measure of the amount of information sent. We prove a number of results in this area. One of them looks at how much a little advice can help Alice and Bob.
Cake Cutting: The fair division of resources is an important topic, be it settling a divorce, resolving international issues such as contested underwater mining territories, or simply cutting a cake. The task is about figuring out how to divide the resource so that each of the n recipient feels they've received a fair portion based on their needs and desires. The best algorithm achieves this with O(n log n) operations, where each operation either asks a recipient to either specify how much they value a particular piece or where they would cut the cake to produce a piece of a given value. We prove a matching lower bound. We also reduced the time to only O(n) operations by allowing the algorithm to flip coins and to provide an approximately fair solution. Interestingly enough, this work was written about in the Toronto Star [Feb 12, 2006. pg. D.16] We give a faster randomized algorithm that is in https://en.wikipedia.org/wiki/EdmondsPruhs_protocol
Greedy and Dynamic Programming Algorithms: The goal of this research area is to define a model of computation, prove that it to some extent captures an algorithm paradigm (in this case greedy algorithms or dynamic programming) because many of the key algorithms in this paradigm can be implemented in the model, and then to prove that other computational problems cant be solved efficiently in this model. We have a number of results in this area.
Embedding Distortion: The adversary places n points in the plane. For every pair of points, he tells me the distance between each pair distorted by factor of at most 1+epsilon. My task, without knowing the original placement, is to again place the points in plane in a way that respects the stated distances within a factor of 1+epsilon'. Surely for small epsilon and reasonably large epsilon', the problem is easy. Surprisingly, we did prove that the problem is NPhard when 1+epsilon is 3.62 and 1+epsilon' is 3.99. My conjecture, is that it is polytime for epsilon' > 2 epsilon and NPhard for epsilon' < 2 epsilon.
TimeSpace Tradeoff Lower Bounds for stConnectivity on JAG Models: The computational problem stconnectivity is to determine whether there is a path from vertex s to vertex t in a graph. The model considered is the JAG (``jumping automaton for graphs'') introduced by Cook and Rackoff in which pebbles are moved around the vertices of the input graph. It is a very natural structured model and is powerful enough so that most known algorithms can be implemented on it. We prove tight lower bounds on how the required time increases exponentially as the space (# of memory cells) available decreases.
Complexity Classes: Instead of studying classes of decision problems based on their computation times, Papadimitriou, Schafer, and Yannakakis categorized search problems into a number of complexity classes. This is particularly important when the associated decision problem is not known to be in P nor to be NPcomplete and when the object being searched for is known to always exist. Our paper studies these classes and proves some equivalences and separations among them.
Circuit Depth: Parallel computation is important but not well understood. The next significant hurdle is proving that there is a problem that cannot be solved on a circuit (and, or, not) with only O(log n) depth (i.e. separate NC^1 from NC^2). Towards this goal, Karchmer, Raz, and Wigderson suggested the intermediate step of proving a lower bound on a slightly simplified version of their communication game characterization of circuit depth, which they call the Universal Composition Relation. Our paper gives an almost optimal lower bound for this intermediate problem.
Comparisons Between Models of Parallel Computation: For my masters, I used Ramsey theory and information theory to separate to models of parallel computation. This provided a greater understanding of the partial information a processor learns about the input.
Job DAG: We consider the problem of computing bounds on the variance and expectation of the longest path length in a DAG from knowledge of variance and expectation of edge lengths. We present analytic bounds for various simple DAG structures, and present a new algorithm to compute bounds for more general DAG structures. Our algorithm is motivated by an analogy with balance of forces in a network of ``strange'' springs. The problem has applications in reliability analysis and probabilistic verification of interface systems.
Data Bases: As part of data mining, we give a fast single scan algorithm for finding all maximal empty rectangles in large twodimensional data sets. IBM bought the patent from us.
Data Transmission: In current transmission networks, packets of data often get lost in chaotic bursts. Applications such as video conferencing and video on demand suffer because the image ``can break up with a jarring abruptness'' even when a only few packets have been lost. We introduce a novel approach called Priority Encoding Transmission (PET) that ensures the video image will degrade gracefully with the number of packets lost, independent of which packets are lost.