Algorithms and Complexity Seminars

Li-Yang Tan: Fooling intersections of low-weight halfspaces
Thursday, November 2, 2017 - 3:00pm to 4:00pm

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$

Andrej Risteski: Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
Wednesday, November 1, 2017 - 4:00pm to 5:00pm

A key task in Bayesian statistics is sampling from distributions that are only specified up to a partition function (i.e., constant of proportionality).

Pritish Kamath: Non-Interactive Agreement & Dimension Reduction for Polynomials
Wednesday, October 25, 2017 - 4:30pm to 5:30pm

The "Non-interactive Agreement Distillation" problem, specified by a joint distribution P(x,y) and a target alphabet size k, is defined as follows: Two players, Alice and Bob, observe sequences (X_1, ... , X_n) and (Y_1, ...

Lijie Chen:On The Power of Statistical Zero Knowledge
Wednesday, October 11, 2017 - 4:00pm to 5:00pm

We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants.

Yuval Dagan: Trading Information Complexity for Error
Thursday, September 28, 2017 - 3:00pm to 4:00pm

We consider the standard two-party communication model. The central
problem studied in this article is how much one can save in
information complexity by allowing an error. Our major result is that

Paul Hand: Deep Compressed Sensing
Wednesday, September 27, 2017 - 4:00pm to 5:00pm

Combining principles of compressed sensing with deep neural network-based generative image priors has recently been empirically shown to require 10X fewer measurements than traditional compressed sensing in certain scenarios.

Yuval Dagan: Detecting Correlations with Little Memory and Communication
Wednesday, March 21, 2018 - 4:00pm to 5:00pm

We study the problem of identifying correlations in multivariate data, under information constraints: Either on the amount of memory that can be used by the algorithm, or the amount of communication when the data is distributed across several machines.

Paul Hand: Deep Compressed Sensing
Wednesday, September 27, 2017 - 4:00pm to 5:00pm

Combining principles of compressed sensing with deep neural network-based generative image priors has recently been empirically shown to require 10X fewer measurements than traditional compressed sensing in certain scenarios.

Clément Canonne: Fifty Shades of Adaptivity (in Property Testing)
Wednesday, April 5, 2017 - 4:00pm to 5:00pm
Adaptivity is known to play a crucial role in property testing. In
particular, there exist properties for which there is an exponential gap
Dean Doron: Explicit two-source extractors for near-logarithmic min-entropy
Wednesday, March 15, 2017 - 4:00pm to 5:00pm


In this talk, we show an explicit construction of extractors for two independent sources of near-logarithmic min-entropy.
Previous constructions required either polylog(n) min-entropy or more than two sources.

Pages

Subscribe to Algorithms and Complexity Seminars