In recent joint work with Alex Arkhipov, we proposed a quantum optics experiment, which would sample from a probability distribution that we believe cannot be sampled (even approximately) by any efficient classical algorithm, unless the polynomial hierarchy collapses. Several optics groups are already working toward doing our experiment.
Computer Science and Discrete Mathematics (CSDM)
Infinite continuous graphs emerge naturally in the geometric analysis of closed planar sets which cannot be presented as countable union of convex sets. The classification of such graphs leads in turn to properties of large classes of real functions - e.g. the class of Lipschitz continuous functions - and to meta-mathematical properties of sub-ideals of the meager ideal (the sigma-ideal generated by nowhere dense sets over a Polish space) which reduce to finite Ramsey-type relations between random graphs and perfect graphs.
A perfect matching in a k-uniform hypergraph H = (V, E) on n vertices
is a set of n/k disjoint edges of H, while a fractional perfect matching
in H is a function w : E → [0, 1] such that for each v ∈ V we have
e∋v w(e) = 1. Given n ≥ 3 and 3 ≤ k ≤ n, let m be the smallest
integer such that whenever the minimum vertex degree in H satisfies
δ(H) ≥ m then H contains a perfect matching, and let m∗ be defined
analogously with respect to fractional perfect matchings. Clearly, m∗ ≤
We give an elementary proof of a generalization of Bourgain and Tzafriri's Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace.
Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(nh) copies of H can be made H-free by removing o(n2) edges. We give a new proof which avoids Szemeredi's regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.
Let $f(x_1,...,x_n)$ be a low degree polynomial over $F_p$. I will prove that there always exists a small set $S$ of variables, such that `most` Fourier coefficients of $f$ contain some variable from the set $S$. As an application, we will get a derandomized sampling of elements in $F_p^n$ which `look uniform` to $f$.
The talk will be self contained, even though in spirit it is a continuation of my previous talk on pseudorandom generators for $CC0[p]$. Based on joint work with Amir Shpilka and Partha Mukhopadhyay.
In our work we study the structure of polynomials of degree three and four that have high bias or high Gowers norm, over arbitrary prime fields. In particular we obtain the following results.