Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Some basic problems and results from Invariant Theory

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
March 7, 2017

Invariant theory deals with properties of symmetries - actions of groups on sets of objects.

It has been slower to join its sibling mathematical theories in the computer science party, but we now see it more and more in studies of computational complexity, pseudorandomness, and the analysis of algorithms.

 

Interactive coding with nearly optimal round and communication blowup

Yael Kalai
Microsoft Research
March 6, 2017

The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since these seminal works, there have been many follow-up works which improve the error rate, the communication rate, and the computational efficiency.

Structural and computational aspects of Brascamp-Lieb inequalities

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
February 28, 2017
The celebrated Brascamp-Lieb (BL) inequalities are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory, with many used in computer science. I will survey the well-understood structural theory of BL inequalities, and then discuss their computational aspects. Far less was known about computing their main parameters, and I will discuss new efficient algorithms (via operator scaling) for those, which also inform structural questions.

New insights on the (non)-hardness of circuit minimization and related problems

Eric Allender
Rutgers University
February 27, 2017
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 present new results relating the complexity of various approximation problems related to MCSP and MKTP. We show that, under modest cryptographic assumptions, some of these approximation problems must have intermediate complexity: they have no solution in P/poly and are not NP-hard under P/poly reductions.

A unified duality-based approach to Bayesian mechanism design

Matt Weinberg
Princeton University
February 14, 2017

We provide a duality framework for Bayesian Mechanism Design. Specifically, we show that the dual problem to revenue maximization is a search over virtual transformations. This approach yields a unified view of several recent breakthroughs in algorithmic mechanism design, and enables some new breakthroughs as well. In this talk, I'll:

1) Provide a brief overview of the challenges of multi-dimensional mechanism design.

2) Construct a duality framework to resolve these problems.

Nearest neighbor search for general symmetric norms via embeddings into product spaces

Ilya Razenshteyn
Massachusetts Institute of Technology
February 13, 2017
I will show a new efficient approximate nearest neighbor search (ANN) algorithm over an arbitrary high-dimensional *symmetric* norm. Traditionally, the ANN problem in high dimensions has been studied over the $\ell_1$ and $\ell_2$ distances with a few exceptions. Thus, the new result can be seen as a (modest) step towards a "unified theory" of similarity search.

Strongly Refuting Random CSPs below the spectral threshold

Prasad Raghavendra
University of California, Berkeley
February 6, 2017
Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with $n$ variables and $m$ clauses, there is a value of $m = \Omega(n)$ beyond which the CSP will be unsatisfiable with high probability. Strong refutation is the problem of certifying that no variable assignment satisfies more than a constant fraction of clauses; this is the natural algorithmic problem in the unsatisfiable regime (when $m/n=\omega(1)$).