theoryseminar2000

Theory Seminar: Schedule for Fall 2000

Milena Mihail
Date: Tuesday, Sept 12, 2000
Time: 4:30-6:00 pm
Room: CoC 354

On the Complexity of the View Selection Problem

``View Selection'' formalizes a widely used preprocessing technique for query response optimization over very large databases; the model was introduced by Ullman and his students. In this talk we will review Ullman's model and focus on the corresponding optimization problem: the problem is NP-complete, thus the focus is on heuristics. This is joint work with Howard Karloff.

Nisheeth Vishnoi
Date: Tuesday, Sept 19,2000 and Sept 26,2000
Time: 4:30-6:00pm
Room: CoC 354

Construction and Applications of Small Bias Probability Spaces

In this survey talk we present construction and application of probability spaces on n random variables which are "almost" k-wise independent. The size of the space is exponential in k and log(1/eps). Eps is the measure of how far the random variables are from being k-wise independent. The natural application of these is in derandomization (when k=O(log n) and 1/eps is polynomial in n). This is based mainly on papers by -{Naor&Naor},{Berger &Rompel}, {Alon, Goldreich,Hastad,Peralta},{Alon,Babai,Itai},{Motwani,Naor,Naor}.

Saugata Basu
Date: Tuesday, Oct 3 ,2000
Time: 4:30-5:30pm
Room: CoC 354

Algorithmic Algebraic Geometry.

Algorithmic algebraic geometry is a basic ingredient for solving numerous applied problems including robot motion planning, geometric modeling, computer-aided design, geometric theorem proving, discrete and computational geometry, molecular chemistry etc. But it has applications in complexity theory as well as, in proving lower bounds in certain non-uniform models of computations. In this talk I will present a general survey of different algorithmic problems of semi-algebraic geometry. I will explain quantifier elimination, algorithms for deciding connectivity questions, some results on the topological complexity of semi-algebraic sets, and give a few applications in the areas of lower bounds, complexity of geometric arrangements and constraint databases.

Dana Randall
Date: Tuesday, Oct 10,2000
Time: 4:30-5:30pm
Room: CoC 354

Glauber dynamics are rapidly mixing for hard-core models in one dimension

We propose a definition of general one-dimensional hard-core statistical physics models and prove by a coupling argument that Glauber dynamics are rapidly mixing on all those models, with mixing time O(n^2 log n) for configurations of length n. We also propose a parallel algorithm which we prove is mixing in time O(log n). The talk will introduce the model and give an overview of the techniques used to show rapid mixing. (Joint work with Claire Kenyon.)

Aranyak Mehta
Date: Tuesday, Oct 17,2000
Time: 4:30-5:30pm
Room: CoC 354

Graph Embeddings

Geometric representations of graphs is an interesting field of study, wherein "good" embeddings of graphs show surprising relations between graph theoretic properties of the graph and geometric properties of its embedding. (An embedding of a graph is simply a map from the vertices of the graph to some space, for example drawing a graph on paper). Examples of such graph-theoretic properties include connectivity, max-cuts, bandwidth, planarity and graph-separators. In interesting cases "good" representations of graphs lead to algorithms to solve graph-theoretic questions. The focus of the talk shall be on the result of Linial, Lovasz and Widgerson on "Rubber bands, convex embeddings, and graph connectivity". This is a very representative example of how geometry of the embedding (dimensions of affine spaces of certain subsets of vertices) gives information about a graph theoretical property (connectivity). The "good" embedding in this case is a "convex" embedding. This relation also leads to a randomised algorithm for computing connectivity. If time permits, the talk will also touch upon several other interesting examples of embeddings - related to bandwidth, max-cut and planarity.

Oct 24, 2000: Holiday

Ion Mandoiu
Date: Tuesday, Oct 31,2000
Time: 4:30-5:30pm
Room: CoC 354

Approximation Algorithms for Buffered Steiner Trees

A buffered Steiner tree is a Steiner trees partitioned into edge disjoint subtrees via a set of buffers, which can be placed either at vertices of the original tree, or on its edges. Buffered Steiner trees have applications in VLSI routing and wireless network design. In these applications buffers represent repeaters that need to be inserted in the interconnection tree in order to meet propagation delay, signal integrity, and power consumption constraints. These constraints are typically modeled as upper-bounds on the length of each edge or buffer-driven subtree, and the goal is to find a buffered Steiner tree with minimum number of buffers for a given set of terminals. In this talk I will present approximation algorithms for several versions of the above buffered Steiner tree problem and formulate some open problems.

Parikshit Gopalan
Date: Tuesday, Nov 7,2000
Time: 4:30-5:30pm
Room: CoC 354

Expanders and Sorting

The first part of this talk will be on "Matching Nuts and Bolts". {Alon, Blum, Fiat, Kannan, Naor, Ostrovsky}. The problem is defined as follows. A carpenter has a set of nuts {s_1 ... s_n} of different diameters and a set of bolts {t_1 .. t_n} such that there is a matching nut for each bolt. The carpenter wants to match the nuts and bolts together. For this, he is only allowed comparisons between a nut and a bolt, he can compare a nut s to a bolt t and say that either s is bigger than t, smaller than t or that they match each other. There is a trivial O(n^2) deterministic algorithm for this and a simple randomized algorithm analogous to quicksort which runs in expected time O(n log n). Getting a deterministic algorithm which runs in time o(n^2) seems a non trivial task. We shall present a deterministic O(n log^4 n) algorithm which uses expanders. The second part of this talk will be a brief review of the problem of sorting in parallel. We shall discuss lower bounds and the best known algorithms like Cole's mergesort and the AKS network. {And if time permits, some work which was done by the speaker for his B. Tech project.)

Nov 14, 2000: FOCS

Amin Saberi
Date: Tuesday, Nov 21,2000
Time: 4:30-5:30pm
Room: CoC 354

Defining Set of a Combinatorial Object

In this talk, I will introduce the concept of defining set for two combinatorial objects: latin squares and strongly connected graphs. A defining set of a latin square is a set of elements in a latin square which can be embedded in only one latin square. Also if any element of the defining set is deleted the remaining set can be embedded in more than one latin square. I will present some results and open problems about the size and structure of latin squares. The defining set can be defined for other combinatorial objects in the same way. The concept of defining sets is also studied for some other combinatorial objects like block design, graph coloring, and graph orientation. I will also present some new results about the structure of the defining set of strongly connected graphs.

Evangelos Markakis
Date: Tuesday, Nov 28,2000
Time: 4:30-5:30pm
Room: CoC 354

Spectral Techniques in Algorithms

The spectrum of a graph (i.e. the eigenvalues and eigenvectors of the adjacency matrix) encodes some detailed structural information about it. The ability to compute the eigenvalues and eigenvectors of a graph in polynomial time provides us with a powerful tool for the design of various graph algorithms. So far, spectral properties have been useful in designing algorithms for problems such as graph bisection, vertex expansion, edge expansion, graph coloring and maximum-clique. In this talk, I will present an algorithm for the maximum-clique problem on randomly generated input graphs, which is based on spectral techniques. The algorithm is by Alon, Krivelevich and Sudakov.

Winter Break