Rutgers/DIMACS
Theory of Computing Seminar
Spring 2014
Place: CoRE 301 (NOTE THE NEW ROOM FOR THIS
SEMESTER)
Time: Wednesdays 11:00 am --
12:00 Noon
Organizers: Swastik Kopparty and Shubhangi
Saraf
Directions
For those arriving by train to New Brunswick station, the best way
to get to the seminar room is by Rutgers bus. The directions are available by
clicking here.
For those driving in, the best strategy is to pre-arrange to pick up a parking
tag from one of the organizers upon arrival, and park in lot 64. For directions
to Lot 64, click on this link.
Links
·
The Rutgers discrete
math seminar.
·
Other Math and CS seminars at
Rutgers.
·
Theory of Computing seminars from previous
semesters.
Schedule
January 22 |
|
Talk cancelled
due to snow |
January 29 |
Aleksandar Nikolov Rutgers University |
Approximating
Hereditary Discrepancy via Small Width Ellipsoids The Discrepancy of a hypergraph
is the minimum attainable value, over two-colorings of its vertices, of
the maximum absolute imbalance of any hyperedge.
The Hereditary Discrepancy of a hypergraph, defined
as the maximum discrepancy of a restriction of the hypergraph
to a subset of its vertices, is a measure of its complexity. Lovasz, Spencer and Vesztergombi
(1986) related the natural extension of this quantity to matrices to rounding
algorithms for linear programs, and gave a determinant based lower bound on
the hereditary discrepancy. Matousek (2011) showed
that this bound is tight up to a polylogarithmic
factor, leaving open the question of actually computing the bound. Recent
work by Nikolov, Talwar
and Zhang (2013) showed a polynomial time O(log^3
n)-approximation to hereditary discrepancy, as a by-product of their work in
differential privacy. In this paper, we give a direct and simple O(log^{3/2} n)-approximation algorithm for this problem.
We show that up to this approximation factor, the hereditary discrepancy of a
matrix A is characterized by the optimal value of simple geometric convex
program that seeks to minimize the largest infinity norm of any point in a ellipsoid containing the columns of A. Joint work with Kunal Talwar. |
February 5 |
|
Talk cancelled
due to freezing rain Rescheduled to
the discrete math seminar: Feb 18, 2pm –
3pm, Hill 525. Click here for more
information |
February 12 |
Bernard Chazelle Princeton University |
Algorithmic
Tools for Self-Organization Just as physics speaks the language of
mathematics, the life sciences speak the language of algorithms. The
difference lies in the loss of symmetry and the high descriptive and
historical complexity of the systems commonly found in social and biological
organisms. This talk will discuss the power of "natural algorithms"
through the lens of "influence systems," a broad family of
high-dimensional self-organizing systems for which algorithmic tools can do
what differential equations cannot. |
February 19 |
Joshua Grochow Univ. of Toronto |
New
connections between lower bounds on algorithms, circuits, and proofs NP versus coNP is the
very natural question of whether, for every graph that doesn't have a
Hamiltonian path, there is a short proof of this fact. One of the arguments
for the utility of proof complexity is that by proving lower bounds against
stronger and stronger proof systems, we "make progress" towards
proving NP is different from coNP. However, until
now this argument has been more the expression of a philosophy or hope, as
there is no known proof system for which lower bounds imply computational
complexity lower bounds. We remedy this situation by introducing a very
natural algebraic proof system*, which has very tight connections to
(algebraic) circuit complexity. We show that any lower bound on any boolean tautology in our proof system implies that the
permanent does not have polynomial-size algebraic constant-free circuits over
any ring (VNP^0 \neq VP^0). Note that, prior to our
work, essentially all implications went the opposite
direction - a circuit complexity lower bound implying a proof complexity
lower bound. This allows us to give a very simple and
completely self-contained proof that NP not in coMA
implies ParityP/poly differs from NC^1/poly, by
applying the preceding result over F_2. Our proof system also has the
advantage that it begins to make clear and precise how much harder it is to
prove lower bounds in algebraic proof complexity than in algebraic circuit
complexity. It thus helps explain why it has been so difficult to prove true
size lower bounds on algebraic proof systems, and thereby also lower bounds
on AC^0[p]-Frege systems (a > 30-year barrier).
Finally, we flip this difference in hardness on its head, to suggest a new
way to transfer techniques from algebraic proof complexity, such as the
method of partial derivatives, to prove lower bounds in algebraic proof
complexity. Joint work in progress with Toniann Pitassi. * - As with many algebraic proof systems, a proof
is checkable in probabilistic polynomial time. |
February 26 |
NO SEMINAR |
|
March 5 |
Anindya De IAS |
Central limit
theorem for Gaussian chaos and deterministic counting for polynomial
threshold functions It is a well-known fact that linear combinations
of Gaussians are Gaussians. What about polynomial combinations? In this talk,
we will see a new central limit theorem for polynomials of Gaussians. The
techniques will draw from the so-called "Stein's method" in
probability theory and Malliavin calculus. As the
main application, we will give the first deterministic polynomial time
algorithm for approximate counting of any constant degree PTF with subconstant error. This theorem will involve a new
decomposition procedure for polynomial which might be of interest in other
applications as well. Joint work with Rocco Servedio. |
March 12 |
Siu Man Chan Princeton University |
Monotone
Lower Bounds via Fourier Analysis We will discuss lower bounds on combinatorial
models of computation under monotone restrictions, using the Fourier analysis
techniques introduced by Potechin. We will prove
tight size bounds on monotone switching networks for the NP-complete problem
of k-clique, and (if time permits) for an explicit monotone problem by
connecting the P-complete problem of generation with reversible pebble games.
The latter result gives alternative proofs of the separations of m-NC from
m-P and of m-NC^i from m-NC^{i+1}
, different from Raz–McKenzie (Combinatorica
’99). |
March 19 |
NO SEMINAR |
SPRING BREAK |
March 26 |
Ran Raz Weizmann Institute, IAS |
How to
Delegate Computations: The Power of No-Signaling Proofs The Martians built an amazingly fast computer and
they run it to answer the great question of life, the universe and
everything. They claim that the answer is 42. Will they be able to convince
us that 42 is the right answer, assuming that we do not have sufficient
computational power to run the computation ourselves, and that we do not
trust Martians? The problem of delegating computation is a central
problem in cryptography. It considers a setting where one party, the
delegator, wishes to delegate the computation of a function to another party,
the worker. The challenge is that the delegator may not trust the worker, and
thus it is desirable to have the worker ``prove'' that the computation was
done correctly. We show a curious connection between that problem
and the model of multi-prover interactive proofs
that are sound against no-signaling (cheating) strategies, a model that was
studied in relation to multi-prover interactive
proofs with provers that share quantum
entanglement, and is motivated by the physical principle that information
cannot travel faster than light. We prove that the class of languages that have
polynomial-time multi-prover interactive proofs,
that are sound against no-signaling strategies, is exactly EXP. We use this
to give a 1-round delegation protocol for every language in EXP. Joint work with Yael Tauman
Kalai and Ron Rothblum |
April 2 |
Aaron Roth U. Penn. |
Privately
Solving Allocation Problems In this talk, we'll consider the problem of
privately solving the classical allocation problem: informally, how to
allocate items so that most people get what they want. Here, the data that we
want to keep private is the valuation function of each person, which
specifies how much they like each bundle of goods. This problem hasn't been
studied before, and for good reason: its plainly
impossible to solve under the constraint of differential privacy. The
difficulty is that publishing what each person i receives in a high-welfare allocation might necessarily
have to reveal a lot about the preferences of person i,
which is what we are trying to keep private! What we show is that under a
mild relaxation of differential privacy (in which we require that no adversary
who learns the allocation of all people j != i – but crucially not the allocation of person i -- should be able to learn much about the valuation
function of player i) the allocation problem is
solvable to high accuracy, in some generality. Our solution makes crucial use
of Walrasian equilibrium prices, which we use as a
low information way to privately coordinate a high welfare allocation. This is joint work with Justin Hsu, Zhiyi Huang, Tim Roughgarden,
and Steven Wu |
April 9 |
Aditya Bhaskara Google |
Smoothed
Analysis of Tensor Decomposition Low rank decomposition of tensors is a powerful
tool that can been used to learn the parameters of a variety of probabilistic
mixture models. However, tensors pose significant algorithmic challenges, and
tensors analogs of much of the matrix algebra toolkit are unlikely to exist
because of hardness results. Efficient decomposition in the overcomplete case (where rank exceeds dimension) is
particularly challenging. We introduce a smoothed analysis model for studying
these questions and develop an efficient algorithm for tensor decomposition
in the highly overcomplete case (rank polynomial in
the dimension). In this setting, we also show that our algorithm is robust to
inverse polynomial error, a property necessary for learning applications. We use our decomposition algorithm to obtain
results for learning multi-view models and mixtures of axis-aligned Gaussians
where there are many more "components" than dimensions, in a
smoothed analysis framework. We believe this an appealing way to analyze
realistic instances of learning problems, since it allows us to overcome many
of the (hardness related) limitations of using tensor methods. Joint work with Moses Charikar, Ankur Moitra and Aravindan Vijayaraghavan |
April 16 |
Yuval Filmus IAS |
Monotone submodular maximization over a matroid Maximizing a monotone submodular
function over the bases of a matroid is a
fundamental algorithmic question, which generalizes the well-known
NP-complete problem MaxCover. A few years ago, Calinescu, Chekuri, Pál and Vondrák developed a
sophisticated algorithm for the problem, the continuous greedy algorithm,
which attains the optimal approximation ratio 1-1/e. Their algorithm combines
a Frank--Wolfe phase together with lossless rounding. We offer an alternative
algorithm attaining the same approximation ratio. Our algorithm is based on a
neglected algorithmic paradigm, non-oblivious local search, in which local
search is run with respect to an auxiliary objective function. Our auxiliary
objective function is also monotone and submodular,
and satisfies the following property: a local optimum with respect to the
auxiliary objective function is a (1-1/e)-approximate *global* optimum with
respect to the original objective function. Joint work with Justin Ward (University of
Warwick). |
April 23 |
Bireswar Das DIMACS/IIT Gandhinagar |
Succinct
Encodings of Graph Isomorphism It is well known that problems encoded with
circuits or formulas generally gain an exponential complexity blow-up
compared to their original complexity. We introduce a new way for encoding graph
problems, based on CNF or DNF formulas. We show that contrary to the other
existing succinct models, there are examples of problems
whose complexity does not increase when encoded in the new form, or
increases to an intermediate complexity class less powerful than the
exponential blow up. We also study the complexity of the succinct
versions of the Graph Isomorphism problem. We show that all the versions are
hard for PSPACE. Although the exact complexity of these problems is not
known, we show that under most existing succinct models the different versions
of the problem are equivalent. We also give an algorithm for the DNF encoded
version of GI whose running time depends only on the size of the succinct
representation. This is a joint work with Patrick Scharpfenecker, Jacobo Torán |
April 30 |
Timothy Naumovitz Rutgers University |
Approximating
distance to monotonicity in the streaming setting Abstract: Given a sequence of integers, one
natural problem that can be considered is the LIS problem, which involves
finding the length of their longest increasing subsequence. The complement of
this problem is known as the distance to monotonicity problem, with the
intuition that the distance to monotonicity of a sequence of integers is the
minimum number of values that would have to be altered to make the sequence
monotone. While one can look at these problems in other settings, we will
focus on the streaming setting, where the sequence of integers is given to us
one at a time and the goal is to minimize the amount of space used. It has been shown by Gopalan,
Jayram, Krauthgamer, and
Kumar that computing these quantities exactly in the streaming setting cannot
be done using sublinear space, so we instead settle
for finding a multiplicative approximation. Previously, Saks and Seshadhri found a polylogarithmic
space randomized algorithm to approximate distance to monotonicity, and we
match this with a polylogarithmic space algorithm
in the deterministic case. Additionally, we provide nontrivial lower bounds
in both the deterministic and randomized cases, which will be discussed if
there is time. This is joint work with Michael Saks. |