Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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.

Bounds on roots of polynomials (and applications)

Adam Marcus
Princeton University; von Neumann Fellow, School of Mathematics
April 18, 2017
I will discuss methods for deriving bounds on the roots of polynomials, and how one can use such bounds to assert the existence of combinatorial structures with certain spectral properties. This will include introducing the "method of interlacing polynomials" and showing how one can use it prove the existence of Ramanujan graphs. Lastly, I will show how one can interpret these methods as a finite version of the previous week's results.

Efficient empirical revenue maximization in single-parameter auction environments

Yannai Gonczarowski
Hebrew University of Jerusalem and Microsoft Research
April 17, 2017
We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneer's revenue in a variety of single-parameter auction environments including matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers.