Rutgers/DIMACS
Theory of Computing Seminar
Fall 2016
Place: CoRE
301 (NOTE
THE ROOM FOR THIS SEMESTER)
Time: Wednesdays 11:00 am --
12:00 Noon
Organizers: Pranjal Awasthi and Swastik Kopparty
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
September 14 |
Prahladh Harsha TIFR (and long-term
visitor at Rutgers/DIMACS) |
On polynomial
approximations to AC0 In this talk, we will discuss some questions related
to polynomial approximations of AC0. A classic result due to Tarui (1991) and
Beigel, Reingold, and Spielman (1991), states that any AC0 circuit of size s
and depth d has an ε-error probabilistic polynomial over the reals of degree
at most (log(s/ε))^{O(d)}. We will have a re-look at this construction and show
how to improve the bound to (log s)^{O(d)}⋅log(1/ε), which is much better
for small values of ε. As an application of this result, we show that (log
s)^{O(d)}⋅log(1/ε)-wise
independence fools AC0, improving on Tal's strengthening of Braverman's theorem
that (log(s/ε))^{O(d)}-wise independence fools AC0. Time permitting, we will
also discuss some lower bounds on the best polynomial approximations to AC0. Joint work with Srikanth Srinivasan |
September 21 |
Bahman Kalantari Rutgers |
Approximating
Nash Equilibrium Via Multilinear Minimax On the one hand we state {\it Nash equilibrium} (NE)
as a formal theorem on multilinear forms and give a pedagogically simple
proof, free of game theory terminology. On the other hand, inspired by this
formalism, we prove a {\it multilinear minimax theorem}, a generalization of
von Neumann's bilinear minimax theorem. Next, we relate the two theorems by
proving that the solution of a multilinear minimax problem, computable via
linear programming, serves as an approximation to Nash equilibrium point,
where its multilinear value provides an upper bound on a convex combination
of {\it expected payoffs}. Furthermore, each positive probability vector once
assigned to the set of players induces a {\it diagonally-scaled} multilinear
minimax optimization with a corresponding approximation to NE. In summary, in
this note we exhibit an infinity of multilinear minimax optimization problems
each of which provides a polynomial-time computable approximation to Nash
equilibrium point, known to be difficult to compute. The theoretical and
practical qualities of these approximations are the subject of further
investigations. |
September 28 |
Guy Even Tel-Aviv University |
A
tale of two local models of computation We consider two models
of computation: centralized local algorithms and local distributed
algorithms. Algorithms in one model
are adapted to the other model to obtain improved algorithms. Distributed vertex
coloring is employed to design improved centralized local algorithms for:
maximal independent set, maximal matching, and an approximation scheme for
maximum (weighted) matching over bounded degree graphs. The improvement is
threefold: the algorithms are deterministic, stateless, and the number of
probes grows polynomially in $\log^* n$, where $n$ is the number of vertices
of the input graph. The recursive
centralized local improvement technique by Nguyen and Onak is employed to
obtain an improved distributed approximation scheme for maximum (weighted)
matching. The improvement is twofold:
we reduce the number of rounds from $O(\log n)$ to $O(\log^* n)$ and our
algorithms are deterministic. Time permitting, a
centralized local algorithm for generating random preferential attachment
graphs will be presented. Per query,
the algorithms uses polylogarithmic random bits, time, and space. Talk based on joint
work with Reut Levy, Moti Medina, Dana Ron, and Adi Rosen. |
October 5 |
NO
SEMINAR |
Avi Wigderson’s Birthday workshop at IAS |
October 12 |
Jakob Nordstrom KTH Stockholm |
Supercritical
Space-Width Trade-offs for Resolution We show that there
are CNF formulas which can be refuted in resolution in both small space and
small width, but for which any small-width resolution proof must have space
exceeding by far the linear worst-case upper bound. This significantly
strengthens the space-width trade-offs in [Ben-Sasson '09], and provides one
more example of trade-offs in the "supercritical" regime above
worst case recently identified by [Razborov '16]. We obtain our results by
using Razborov's new hardness condensation technique and combining it with
the space lower bounds in [Ben-Sasson and Nordström '08]. This is joint work
with Christoph Berkholz. |
October 19 |
Andrej Risteski Princeton University |
Calculating
partition functions using convex programming: provable bounds for variational
methods Abstract: The problem of approximating partition
functions for graphical models is a very important one: from a practical
point of view it is linked intimately to common tasks like calculating
marginals and sampling from the model; from a theoretical it is linked to
understanding the class #P, which intuitively captures counting problems. We give provable bounds for algorithms that are
based on variational methods: a technique which is very popular in practice
but rather poorly understood theoretically in comparison to Markov Chain
Monte Carlo methods. We make use of recent tools in combinatorial
optimization: the Sherali-Adams and Sum of Squares convex programming
hierarchies to get algorithms for "dense" Ising models. These
techniques give new, non-trivial approximation guarantees for the partition
function beyond the regime of correlation decay. They also generalize some
classical results from statistical physics about the Curie-Weiss model, as
well as provide a partition function counterpart of classical results about
max-cut on dense graphs. With this, we connect tools from two apparently
disparate research areas -- optimization and counting/partition function
approximations. Our proof techniques are very simple and generic, and likely
to be applicable to other settings. |
October
26 |
Orit Raz IAS/DIMACS |
The
Elekes-Szab'o problem and applications to combinatorial geometry Let
F(x,y,z) be a real trivariate polynomial of constant degree, and let A,B,C be
three sets of real numbers, each of size n. How many points of A x B x C can
lie on {F=0}? This question has been studied by Elekes and R\'onyai and then
by Elekes and Szab\'o about 15 years ago. In
the talk I will review some recent results concerning this problem and its
variants, and introduce some applications of the results to problems in
extremal combinatorial geometry. |
November 2 |
Alekh Agrarwal Microsoft Research |
Sample-efficient
Reinforcement Learning with Rich Observations Abstract: This talk considers a core question in
reinforcement learning (RL): How can we tractably solve sequential decision
making problems where the learning agent receives rich observations? We begin
with a new model called Contextual Decision Processes (CDPs) for studying
such problems, and show that it encompasses several prior setups to study RL
such as MDPs and POMDPs. Several special cases of CDPs are, however, known to
be provably intractable in their sample complexities. To overcome this
challenge, we further propose a structural property of such processes, called
the Bellman Rank. We find that the Bellman Rank of a CDP (and an associated
class of functions) provides an intuitive measure of the hardness of a
problem in terms of sample complexity. In particular, we propose an
algorithm, whose sample complexity scales with the Bellman Rank of the
process, and is completely independent of the size of the observation space
of the agent. We also show that our techniques are robust to our modeling
assumptions, and make connections to several known results as well as
highlight novel consequences of our results. This talk is based on joint work with Nan Jiang,
Akshay Krishnamurthy, John Langford and Rob Schapire. |
November 9 |
Pravesh Kothari Princeton
University |
A nearly tight
sum of squares lower bound for planted clique We prove that with high probability over the draw of
a graph from the Erdös-Renyi distribution G(n,1/2), the ~n^d time, degree d
sum of squares relaxation for the clique problem gives a value of
~n^{1/2-o(1)} for any d = o(\log(n)). This yields a nearly tight n^{1/2-o(1)}
lower-bound on the value of this program for any degree d=o(logn). Key to the proof is a new framework that we call
pseudo-calibration to construct Sum of Squares lower bounds. This framework
is inspired by taking a computational analog of Bayesian probability theory.
It yields a general recipe for constructing good pseudo-distributions (i.e.,
dual certificates for the Sum-of-Squares semidefinite program), and sheds
further light on the ways in which this hierarchy differs from others. |
November 16 |
Eric Allender Rutgers |
New
Insights on the (Non)-Hardness of Circuit Minimization and Related Problems The
Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals
with time-bounded Kolmogorov complexity are prominent candidates for
NP-intermediate status. We prove new unconditional lower bounds for MKTP, by
showing that MKTP is hard for the complexity class DET (a class that captures
the complexity of computing the determinant; DET contains NL) under
non-uniform NC0 reductions. Under
a suitable derandomization hypothesis, we obtain uniform reductions, and we
are even able to show that circuit size lower bounds are equivalent to
hardness results for certain problems related to MKTP, and provide the first
results showing that hardness of MCSP problems implies hardness for MKTP
problems. We also present new results relating the complexity of various
promise problems related to MCSP and MKTP. We show that, under modest
cryptographic assumptions, some of these promise problems must have
intermediate complexity: they have no solution in P/poly and are not NP-hard
under P/poly reductions. Joint
work with Shuichi Hirahara. |
November 23 |
NO
SEMINAR |
(FRIDAY SCHEDULE) |
November 30 |
Pooya Hatami DIMACS |
Pseudorandom
Generators for Low Sensitivity Functions In this talk, we discuss a new PRG (pseudorandom
generator) for low sensitivity functions. The sensitivity of a Boolean
function f is the maximum, over all inputs x, of the number of sensitive
coordinates of x (namely, the number of Hamming neighbors of x with different
f-value). We give a PRG with seed-length 2^(sqrt(s)) that fools Boolean
functions with sensitivity at most s. Even though assuming the well-known
sensitivity conjecture of Nisan and Szegedy would imply a PRG of seed-length
poly(s) for functions of sensitivity s, no PRG with seed-length
subexponential in s(f) was known before our work. Our construction is based on a derandomized
switching lemma for low sensitivity functions. Based on joint work with Avishay Tal and Li-Yang
Tan. |
December 7 |
Ankit Garg Princeton
University |
Algorithmic and
optimization aspects of Brascamp-Lieb inequalities The celebrated Brascamp-Lieb (BL) inequalities (and
their extensions) are an important mathematical tool, unifying and
generalizing numerous inequalities in analysis, convex geometry and
information theory. While their structural theory is very well understood, far
less is known about computing their main parameters. We give polynomial time
algorithms to compute: - Feasibility of BL-datum - The optimal BL-constant - A weak separation oracle for the BL-polytope The algorithms are obtained by a simple efficient
reduction of a given BL-datum to an instance of the Operator Scaling problem
defined by Gurvits, for which the present authors provided a polynomial time
algorithm recently. Based on joint work with Leonid Gurvits, Rafael
Oliveira and Avi Wigderson. |