Abstract:
We give near-tight lower bounds for the sparsity required in
several dimensionality reducing linear maps. In particular, we
show:
(1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse
Johnson-Lindenstrauss lemma is optimal...
For a set of polynomials F, we define their bilinear complexity
as the smallest k so that F lies in an ideal generated by k
bilinear polynomials. The main open problem is to estimate the
bilinear complexity of the single polynomial
$\sum_{i,j}x_i^2...
We will give an overview of this system, which has been at the
center of recent algorithmic and proof complexity developments. We
will give the definitions of the system (as a proof system for
polynomial inequalities, and as an SDP-based algorithm)...
In this talk we will discuss information complexity -- a measure
of the amount of information Alice and Bob need to exchange to
solve a problem over distributed inputs. We will present an
information-theoretically optimal protocol for computing the...
For all practical purposes, the Micali-Vazirani algorithm,
discovered in 1980, is still the most efficient known maximum
matching algorithm (for very dense graphs, slight asymptotic
improvement can be obtained using fast matrix
multiplication)...
The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the
existence of proofs that can be verified by reading a very small
part of the proof. Since the discovery of the theorem, there has
been a considerable work on improving the theorem in terms...
Some important mechanisms considered in game theory require
solving optimization problems that are computationally hard.
Solving these problems approximately may not help, as it may change
the players’ rational behavior in the original mechanisms...
Polynomial Identity Testing (PIT) is the problem of identifying
whether a given algebraic circuit computes the identically zero
polynomial. It is well-known that this problem can be solved with
small error probability by testing whether the circuit...