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


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


·     The Rutgers discrete math seminar.

·     Other Math and CS seminars at Rutgers.

·     Theory of Computing seminars from previous semesters.



September 14

Prahladh Harsha


(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


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


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


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


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



November 30

Pooya Hatami


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.