2011-2012 Seminars

Partitioning the vertices of a graph into two (roughly) equal parts to minimize the weight of edges cut is a fundamental optimization problem, arising in diverse applications. Despite intense research, there remains a huge gap in our understanding...

In this talk I will present a colored version of Tverberg's theorem about partitioning finite point sets in R^d into rainbow groups whose convex hulls intersect. This settles the famous Bárány-Larman conjecture (1992) for primes minus one, and...

We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that very limited assumptions about x allow one to make successful predictions about unseen bits of x . Our main focus...

A randomness extractor is an efficient algorithm which extracts high-quality randomness from a low-quality random source. Randomness extractors have important applications in a wide variety of areas, including pseudorandomness, cryptography...

To examine the limiting behavior of graph sequences, many discrete methods meet their continuous counterparts, leading to numerous theoretical and applicable advancements. For dense graph sequences, the graph limits have recently been well developed...

The Resolution proof system is among the most basic and popular for proving propositional tautologies, and underlies many of the automated theorem proving systems in use today. I'll start by defining the Resolution system, and its place in the proof...

Milman's ellipsoids play an important role in modern convex geometry. Here we show that their proofs of existence can be turned into efficient algorithms, and these in turn lead to improved deterministic algorithms for volume estimation of convex...

The P vs. NP problem has sometimes been unofficially paraphrased as asking whether it is possible to improve on exhaustive search for such problems as Satisfiability, Clique, Graph Coloring, etc. However, known algorithms for each of these problems...

In the file maintenance problem, n integer items from the set {1,....,r} are to be stored in an array of size m>=n . The items are presented sequentially in an arbitrary order and must be stored in the array in sorted order (but not necessarily in...

For modern SAT solvers based on DPLL with clause learning, the two major bottlenecks are the time and memory used by the algorithm. This raises the question of whether this memory bottleneck is inherent to Resolution based approaches, or an artifact...