# Algorithms and Complexity Seminars

 Li-Yang Tan: Fooling intersections of low-weight halfspacesThursday, November 2, 2017 - 3:00pm to 4:00pmA 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 givean 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 CarloWednesday, November 1, 2017 - 4:00pm to 5:00pmA 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 PolynomialsWednesday, October 25, 2017 - 4:30pm to 5:30pmThe "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 KnowledgeWednesday, October 11, 2017 - 4:00pm to 5:00pmWe examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. Yuval Dagan: Trading Information Complexity for ErrorThursday, September 28, 2017 - 3:00pm to 4:00pmWe consider the standard two-party communication model. The centralproblem studied in this article is how much one can save ininformation complexity by allowing an error. Our major result is that Paul Hand: Deep Compressed SensingWednesday, September 27, 2017 - 4:00pm to 5:00pmCombining 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 CommunicationWednesday, March 21, 2018 - 4:00pm to 5:00pmWe 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:00pmCombining 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. Inparticular, there exist properties for which there is an exponential gap Dean Doron: Explicit two-source extractors for near-logarithmic min-entropyWednesday, March 15, 2017 - 4:00pm to 5:00pmIn 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.