YALE 2004 WORKSHOP on DISCRETE MATHEMATICS and THEORETICAL COMPUTER SCIENCE

List of Open problems and links to papers will be added shortly.

http://cs-www.cs.yale.edu/homes/kalai/workshop04.html

From Monday afternoon, September 27, 2004 until Wednesday, September 29, 2004.

This year Workshop's theme:

Harmonic Analysis of Boolean functions

Organizers: Gil Kalai and Ravi Kannan

Participants:

Adi Akavia (M.I.T.), Mikhail V. Alekhnovitch (I.A.S), Sanjeev Arora (Princeton), Dana Angluin (Yale), Boaz Barak (I.A.S), Jim Aspnes (Yale), Don Brown (Yale), Raphy Coifman (Yale), Josh Cooper (NYU), Mike Fischer (Yale), Ehud Friedgut (HU), Jeff Jackson (Duquesne U), Elad Hazan(Princeton), Gil Kalai (Yale and HU), Satyen Kale (Princeton), Ravi Kannan (Yale), Guy Kindler (I.A.S), Bo'az Klartag (I.A.S), Adam Klivans (Toyota Tech. Inst./UT-Austin), Gadi Kozma (I.A.S), Nati Linial (Microsoft and HU), Konstantin Makarychev (Princeton), Yury Makarychev (Princeton), Ryan O'Donnell (Microsoft), Sasha Razborov (I.A.S), Muli Safra (I.A.S., Princeton U. and TAU), Mike Saks (Rutgers), David Sattinger (Yale), Herb Scarf (Yale), Rocco Servadio (Columbia), Joel Spencer (NYU), Dan Spielman (MIT and Yale), Christino Tamon (Clarkson) Sekhar Tatikonda (Yale), Van Vu (UCSD), Avi Wigderson(IAS), Steve Zucker (Yale).

The hotel where participants stay is: The Colony INN, 1157 Chapel street New Haven. It is 10-15 minitues walking distance from the CS and Math departments. Support for lodging in New Haven for additional participants (also grad. students) is still available!

Open problems: Fourier analysis of boolean functions and related topics (under construction)

Program

Discrete Math and theoretical CS seminar

Monday, September 27, 4:30 AKW (CS building) room 200

Title: Divide and Conquer Martingales and Distribution of random Polytopes

Tuesday, September 28, Morning session: AKW (CS building) Room 200

9:00 - Gathering

9:30 Mike Saks - Influences and decision tree complexity

10:30 Nati Linial: Complexity measures for sign matrices

11:30 Problem Session I

- lunch

Tuesday, September 28, afternoon session: LOM (Math. building) Room 206

2:00 Ryan O'Donnell - Majority Is Stablest.

3:00 Sanjeev Arora - Expander Flows, Geometric Embeddings, and Graph Partitioning

4:30 Jeff Jackson - A survey talk on Fourier analysis and learnability.

Dinner: Scoozi: subsadised price: 15$ grad. students 25$ others.

Wednesday, September 29, Morning session: AKW (CS building) Room 500

9:15 Muli Safra: Approximating the vertex cover.

10:15 Adi Akavia: Proving Hard-Core Predicates Using List Decoding

11:30: LOM (Math. building) Room 206. Ehud Friedgut: Four proofs of an intersection theorem: which is the book proof?

Lunch

Wednesday, September 29, afternoon session: LOM (Math. building) Room 206

2:15 Guy Kindler: Decay of fourier coefficients for bounded real functions on the discrete cube.

3:15 Raphy Coifman: Diffusion geometry on graphs

4:30 - Avi Wigderson - Explicit constructions for Ramsey Bipartite graphs.

Open Problems: links will be added soon.

Abstracts, annotations and links.

Abstract for Van Vu's talk: Divide and Conquer Martingales and Distribution of random Polytopes

Let K be convex body with volume one in R^d. Choose n random points in K with respect to the uniform distribution. The convex hull of these points, denoted by K_n, is a random polytope.

The study of K_n was started by Renyi-Sulanke and Efron about 40 years ago. The goal of this study is to understand the distribution of the key functionals of K_n (such that its volume or its number of vertices).

The expectations of most functionals are known, but little has been achieved beyond this. For instance, there are very few results about higher moments. The main obstacle is that the geometric methods which are efficient for computing the expectation become very difficult to apply for other purposes.

In this talk, we are going to introduce a new method by which one can give fairly accurate estimates concerning the distributions of key functionals of K_n. This helps us to answer several open questions, including the one above about moments. The main tool of our method is the so-called "Divide and Conquer Martingale" technique, a refinement of Azuma's inequality.

Abstract for Mike Saks' lewcture:

I will present two recently proved inequalities relating influence and decision tree computation of boolean functions. Combining these inequalities leads to new general lower bounds for randomized decision tree complexity.

This is joint work with Ryan O'Donnell, Rocco Servedio and Oded Schramm.

Abstract for Nati Linial's lecture

Abstract: We seek ways of studying complexity also outside the realm of computational complexity. In this paper we consider sign matrices. We note that rank meets our general criterion for a complexity measure and consider another three variations on the theme of the rank. All these three complexity measures had been studied before in different contexts, and we carry out a systematic comparison among them. This perspective provides a unifying framework for several known problems and suggests several interesting new problems. To whet your appetite, here is one - Can you suggest an efficient way for sampling sign matrices with low rank?

(Joint work with A. Shraibman, G. Schechtman and S. Mendelson)

Abstract for Ryan O'Donnell's talk:

Let f : {-1,1}^n -> {-1,1} be a boolean function. For 0 < rho < 1, let K_rho(f) denote the "noise correlation" of f with itself: K_rho(f) = E[f(x) f(y)], where x and y are rho-correlated random inputs. In other words, 1/2 + 1/2 K_rho(f) is the probability that f(x) = f(y), when x is a randomly chosen string and y is obtained by flipping each bit of x with probability 1/2 - 1/2 rho.

In a recent paper [KKMO '04] on the hardness of approximating MAX-CUT, it was conjectured that among all f with "small influences", the Majority function maximizes K_rho for each rho. I will sketch a proof of this, just recently worked out with Elchanan Mossel (Berkeley) and Krzysztof Oleszkiewicz (Warsaw).

Abstract for Adi Akavia's talk:

We introduce a unifying framework for proving that predicate $P$ is hard-core for a one-way function $f$, and apply it to a broad family of functions and predicates, reproving old results in an entirely different way as well as showing new hard-core predicates for well known one-way function candidates. Our framework extends the list-decoding method of Goldreich and Levin for showing hard-core predicates. Namely, a predicate will correspond to some error correcting code, predicting a predicate will correspond to access to a corrupted codeword, and the task of inverting one-way functions will correspond to the task of list decoding a corrupted codeword.

A characteristic of the error correcting codes which emerge and are addressed by our framework, is that codewords can be approximated by a small number of heavy coefficients in their Fourier representation. Moreover, as long as corrupted words are close enough to legal codewords, they will share a heavy Fourier coefficient. We list decode such codes, by devising a learning algorithm applied to corrupted codewords for learning heavy Fourier coefficients.

Joint work with Shafi Goldwasser and Muli Safra

Abstract for Sanjeev Arora's talk:

Partitioning a graph into two (or more) large pieces while minimizing the size of the ``interface'' between them is a fundamental combinatorial problem. Graph partitions or separators are central objects of study in the theory of Markov chains, geometric embeddings and are a natural algorithmic primitive in numerous settings, including clustering, divide and conquer approaches, PRAM emulation, VLSI layout, and packet routing in distributed networks.

I will talk about recent developments in developing approximation algorithms for such problems. A paper of mine with Satish Rao and Umesh Vazirani in STOC'04 gave a \sqrt{log n}-approximation for SPARSEST CUT. This improved classical algorithms based upon both spectral methods and multicommodity flows (Leighton Rao; O(log n)-approximation). We also introduced the notion of {\em expander flows}, which constitute an interesting ``certificate'' of a graph's expansion.

All the above results were proved by exhibiting a new structural property of finite metric spaces of "negative type" (a class that contains l_1 and l_2) that has motivated a flurry of followup work (still unpublished) in the past few months giving (i) new approximation algorithms for various problems (ii) new results about embeddings of metric spaces into normed spaces that closed important open problems in mathematics (iii) further structural understanding of phenomena such as expander flows (iv) quadtratic time algorithm for computing expander flows and computing \sqrt{log n} approximation for SPARSEST CUT (this is joint work with students Elad Hazan and Satyen Kale; appearing at FOCS'04), suggesting that these ideas may yield practical algorithms.

Abstract for Ehud Friedgut's talk

The simple theorem on {0,1}^n found below is an analogue of the Erdos-Ko-Rado thm. We will study four different proofs and at the end of the talk vote which (if any) of these proofs is the book proof. Please register to vote prior to October 2'nd, every vote counts!

Thm: Let 0