Usual coordinates:
Friday, 2:00PM
Room 1314
Warren Weaver Hall
251 Mercer Street
Fall 2015 Schedule
Upcoming talks
List of previous talks
Wednesday September 23
11:00AM
WWH 517
Eshan Chattopadhyay (UT Austin)
Title: Explicit Two-Source Extractors and Resilient Functions
Abstract: We explicitly construct an extractor for two independent sources on n bits,
each with min-entropy at least log^C n for a large enough constant C. Our extractor
outputs one bit and has error n^{-\Omega(1)}. The best previous extractor, by Bourgain,
required each source to have min-entropy .499n.
A key ingredient in our construction is an explicit construction of a monotone,
almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta>0.
In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious
bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently,
and the remaining q=n^{1-\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits.
The best previous construction, by Viola, achieved q=n^{1/2 - \delta}.
Our explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey
graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.
Joint work with David Zuckerman.
Friday October 2
2:00PM
WWH 1314
Omri Weinstein (NYU)
Title: Welfare Maximization with Limited Interaction
Abstract:
We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model
where agent's valuations are unknown to the central planner, and therefore communication is required to determine an
efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is n, then r rounds of interaction
(with logarithmic bandwidth) suffice to obtain an n^{1/(r+1)}-approximation to the optimal social welfare. In particular,
this implies that such markets converge to a stable state (constant approximation) in time logarithmic in the market size.
We obtain the first multi-round lower bound for this setup. We show that even if the allowable per-round bandwidth of each
agent is n^{eps(r)}, the approximation ratio of any r-round (randomized) protocol is no better than \Omega(n^{1/5^{r+1}}),
implying an \Omega(\log \log n) lower bound on the rate of convergence of the market to equilibrium.
Our construction and technique may be of interest to round-communication tradeoffs in the more general setting of
combinatorial auctions, for which the only known lower bound is for simultaneous (r=1) protocols [DNO14].
Joint work with Noga Alon, Noam Nisan and Ran Raz.
Friday October 9
2:00PM
WWH 1314
Alexander S. Kulikov (St. Petersburg Department of Steklov Institute of Mathematics)
Title: Generalizations of the Gate Elimination Method
Abstract:
It is known that a random Boolean function on $n$ variables requires
circuits of size $\Theta(2^n/n)$. At the same time, the strongest
known lower bound $3n-o(n)$ for an explicit Boolean function (that is,
a function from NP) was given by Blum more than 30 years ago. This
bound, as well as most of the previous bounds, is based on a simple
method called gate elimination. Its idea is straightforward: roughly,
to prove a lower bound $cn$ for a function from a certain one shows
that in any circuit computing a function from a class one can find a
substitution of a constant to an input variable that eliminates at
least c gates from a circuit and leaves a subfunction from the same
class; the bound then follows by induction.
In this talk, we will discuss ways of generalizing the gate
elimination method for proving circuit lower bounds. First, we will
present a slightly stronger than $3n$ lower bound for affine
dispersers. These are functions that are not constant on any affine
subspace of sufficiently large dimension. Equivalently, such functions
do not degenerate under sufficiently many linear substitutions. We
will then show that an explicit construction of dispersers for
quadratic varieties (currently unknown) implies stronger lower bounds.
Informally, these are functions that survive even under quadratic (but
not only linear) substitutions.
Thursday October 29
12:20PM
WWH 317
Daniel Dadush (CWI)
Title: On the Shadow Simplex Method for Curved Polyhedra
Abstract: We study the simplex method over polyhedra satisfying certain
"discrete curvature" lower bounds, which enforce that the boundary
always meets vertices at sharp angles. Motivated by linear programs with
totally unimodular constraint matrices, recent results of Bonifas et al
(SOCG 2012), Brunsch and Roglin (ICALP 2013), and Eisenbrand and Vempala
(2014) have improved our understanding of such polyhedra.
We develop a new type of dual analysis of the shadowsimplex method which
provides a clean and powerful tool for improving all previously
mentioned results. Our methods are inspired by the recent work of
Bonifas and the first named author (SODA 2015), who analyzed a
remarkably similar process as part of an algorithm for the Closest
Vector Problem with Preprocessing.
For our first result, we obtain a constructive diameter bound of
O(n^2/\delta \ln(n/\delta)) for n-dimensional polyhedra with curvature
parameter \delta \in [0,1]. For the class of polyhedra arising from
totally unimodular constraint matrices, this implies a bound of O(n^3
\ln n). For linear optimization, given an initial feasible vertex, we
show that an optimal vertex can be found using an expected O(n^3/\delta
\ln(n \delta)) simplex pivots, each requiring O(mn) time to compute. An
initial feasible solution can be found using O(mn^3/\delta \ln(n
\delta)) pivot steps.
Joint with Nicolai Hahnle.
Friday October 30
2:00PM
WWH 1314
Adi Rosen (CNRS and Université Paris Diderot)
Title: Semi-Streaming Set Cover
Abstract: We study, under the semi-streaming model, the classical set cover problem.
The underlying set system is formalized in terms of a hypergraph $G = (V, E)$
whose edges arrive one-by-one and the goal is to construct an edge cover
$F \subseteq E$ with the objective of minimizing the cardinality (or cost in the
weighted case) of $F$. We consider a parameterized relaxation of this problem,
where given $0 \leq \epsilon < 1$, the goal is to construct an edge
$(1 - \epsilon)$-cover, namely, a subset of edges incident to all but an
$\epsilon$-fraction of the vertices (or their benefit in the weighted case).
The key limitation imposed on the algorithm is that its memory space is
limited to (poly)logarithmically many bits per vertex.
Our main result is an asymptotically tight trade-off between $\epsilon$ and
the approximation ratio: We design a semi-streaming algorithm that on
input hypergraph $G$, constructs a succinct data structure $D$ such that
for every $\epsilon$, one can extract from $D$ an edge $(1 - \epsilon)$-cover
that approximates the optimal edge ($1$-)cover. The approximation factor is
$1/\epsilon$ for $\epsilon > \sqrt{n}$, and $\sqrt{n}$ for smaller $\epsilon$
(where $n$ is the number of vertices). In particular, for the traditional
set cover problem we obtain an $O(\sqrt{n})$-approximation.
This algorithm is proved to be best possible in the semi-streaming setting
by establishing a family (parameterized by $\epsilon$) of matching lower
bounds.
Joint work with Yuval Emek.
Friday November 6
2:00PM
WWH 1314
Avishay Tal (IAS)
Title: Rigidity of Random Toeplitz Matrices with an Application to Depth Three Circuits
Abstract: We prove that random $n$-by-$n$ Toeplitz matrices over $GF(2)$ have rigidity
$\Omega(n^3 / (r^2 \log n))$ for rank $r > \sqrt{n}$, with high probability. This improves,
for $r = o(n / \log n \log\log n)$, over the $\Omega( (n^2 / r) * \log(n/r) )$ bound that
is known for many explicit matrices.
Our result implies that an explicit trilinear function $f$ on $n$ variables has complexity $\Omega(n^{3/5})$
in the multilinear circuit model suggested by Goldreich and Wigderson (ECCC, 2013), which yields an
$\exp(n^{3/5})$ lower bound on the size of the so-called canonical depth-three circuits for $f$.
