Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Fooling intersections of low-weight halfspaces

Rocco Servedio
Columbia University
October 30, 2017

A weight-$t$ halfspace is a Boolean function $f(x)=\mathrm{sign}(w_1 x_1 + \cdots + w_n x_n - \theta)$ where each $w_i$ is an integer in $\{-t,\dots,t\}.$  We give an explicit pseudorandom generator that $\delta$-fools any intersection of $k$ weight-$t$ halfspaces with seed length poly$(\log n, \log k,t,1/\delta)$. In particular, our result gives an explicit PRG that fools any intersection of any quasipoly$(n)$ number of halfspaces of any polylog$(n)$ weight to any $1/$polylog$(n)$ accuracy using seed length polylog$(n).$

On the strength of comparison queries

Shay Moran
University of California, San Diego; Member, School of Mathematics
October 24, 2017

Joint work with Daniel Kane (UCSD) and Shachar Lovett (UCSD)

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.

For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries. This settles a problem studied by [Meyer auf der Heide ’84, Meiser ‘93, Erickson ‘95, Ailon and Chazelle ‘05, Gronlund and Pettie '14, Gold and Sharir ’15, Cardinal et al '15, Ezra and Sharir ’16] and others.

A nearly optimal lower bound on the approximate degree of AC$^0$

Mark Bun
Princeton University
October 23, 2017

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. For any constant $\delta > 0$, we exhibit an AC$^0$ function of approximate degree $\Omega(n^{1-\delta})$. This improves over the best previous lower bound of $\Omega(n^{2/3})$ due to Aaronson and Shi, and nearly matches the trivial upper bound of $n$ that holds for any function.

Structural aspects of the null-cone problem in invariant theory

Ankit Garg
Microsoft Research
October 10, 2017
Invariant theory studies the actions of groups on vector spaces and what polynomial functions remain invariant under these actions. An important object related to a group action is the null cone, which is the set of common zeroes of all homogeneous invariant polynomials. I will talk about the structural aspects of the null cone from a computational and optimization perspective. These will include the Hilbert-Mumford and Kempf-Ness theorems which imply that null cone membership is in NP intersect coNP (ignoring bit-size issues).

Barriers for rank methods in arithmetic complexity

Rafael Oliveira
University of Toronto
October 9, 2017

Arithmetic complexity is considered (for many good reasons) simpler to understand than Boolean complexity. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, foundational challenges, like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive.

Elementary open problems in Algebra (with consequences in computational complexity)

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
October 3, 2017
I will survey some elementary (to state!) problems on groups, matrices, and tensors, and discuss their motivations arising from several major problems in computational complexity theory. On each problem there was some exciting recent progress which may raise hope it can be resolved. No special background will be assumed.