Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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)$).

Quantifying tradeoffs between fairness and accuracy in online learning

Aaron Roth
University of Pennsylvania
January 30, 2017
In this talk, I will discuss our recent efforts to formalize a particular notion of “fairness” in online decision making problems, and study its costs on the achievable learning rate of the algorithm. Our focus for most of the talk will be on the “contextual bandit” problem, which models the following scenario. Every day, applicants from different populations submit loan applications to a lender, who must select a subset of them to give loans to.

Active learning with "simple" membership queries

Shachar Lovett
University of California, San Diego
January 23, 2017
An active learning algorithm for a classification problem has access to many unlabelled samples. The algorithm asks for the labels of a small number of samples, carefully chosen, such that that it can leverage this information to correctly label most of the unlabelled samples. It is motivated by many real world applications, where it is much easier and cheaper to obtain access to unlabelled data compared to labelled data. The main question is: can active learning algorithms out-perform classic passive learning algorithms?