Back to Events

Seminar Series

July 30

New Algorithms for Conditional Linear Regression

Brendan Juba

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2018-07-30 16:00:00 2018-07-30 17:00:00 America/New_York New Algorithms for Conditional Linear Regression Abstract: The kinds of rules that we know how to fit to data, such as linear rules, are rather limited. Hence we desire algorithms that can find rules that partiallyfit the data. We are particularly interested in cases where the predictor is only valid on a small subset of the data, less than 50%. Recent work on suchtasks often cannot achieve meaningful guarantees for rich problems such as linear prediction or classification without using some extra structure. In the conditional linear regression task, we seek a k-DNF rule describing such a subset of the data distribution on which a low-error linear predictor exists, together with a description of this linear predictor function. I will discuss new algorithms for this problem, for the usual squared-error loss, that find a k-DNF that selects nearly the same fraction of the data as some optimal k-DNF.On the k-DNF we find, we can guarantee for example that there is a linear rule achieving a O~(r log log n) approximation to the loss of the optimal linear ruleon an optimal r-term k-DNF on n attributes, given that the covariance of the distribution on the individual terms does not vary too much.This talk is based on joint works with Calderon, Li, Li, and Ruan; and withHainline, Le, and Woodruff. 32-G575

June 07

Parameterized Intractability of Even Set

Arnab Bhattacharyya
Indian Institute of Science

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2018-06-07 16:00:00 2018-06-07 17:00:00 America/New_York Parameterized Intractability of Even Set Abstract: The k-Even Set problem is a parameterized variant of the Minimum Distance Problemfor binary ?linear codes, which can be stated as follows: given a generator matrix Aand an integer k, determine whether the code generated by A has distance atmost k. Here, k is the parameter of the problem. The question of whetherk-Even Set is fixed parameter tractable (FPT) has been repeatedly raised inliterature and has earned its place in Downey and Fellows' book (2013) asone of the "most infamous" open problems in the field of ParameterizedComplexity.In this talk, I will present our work showingthat k-Even Set does not admit FPT algorithms under the (randomized) GapExponential Time Hypothesis (Gap-ETH). In fact, our result rules out notonly exact FPT algorithms, but also any constant factor FPT approximationalgorithms for the problem. Furthermore, our result holds even under thefollowing weaker assumption, which is also known as the ParameterizedInapproximability Hypothesis (PIH): no (randomized) FPT algorithm candistinguish a satisfiable 2CSP instance from one which is only0.99-satisfiable (where the parameter is the number of variables).?In a subsequent work, Bonnet, Egri, Lin and Marx showed inapproximabilityof the parameterized Nearest Codeword problem, which together with ourresult, implies unconditional W[1]-hardness of Even Set. If there is time,I will also sketch this result.?Joint work with Karthik C.S., Suprovat Ghoshal and Pasin Manurangsi. 32-G575

May 24

On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product

Lijie Chen

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2018-05-24 16:00:00 2018-05-24 17:00:00 America/New_York On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product Abstract : In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets A and B of vectors, and the goal is to find a in A and b in B maximizing inner product between a and b. Max-IP is very basic and serves as the base problem in the recent breakthrough of [Abboud et al., FOCS 2017] on hardness of approximation for polynomial-time problems. It is also used (implicitly) in the argument for hardness of exact l_2-Furthest Pair (and other important problems in computational geometry) in poly-log-log dimensions in [Williams, SODA 2018]. We have three main results regarding this problem. 1. Characterization of Multiplicative Approximation. First, we study the best multiplicative approximation ratio for Boolean Max-IP in sub-quadratic time. We show that, for Max-IP with two sets of n vectors from {0,1}^d, there is an n^{2 - Omega(1)} time (d/log n)^{Omega(1)}-multiplicative-approximating algorithm, and we show this is conditionally optimal, as such a (d/log n)^{o(1)}-approximating algorithm would refute SETH. Similar characterization is also achieved for additive approximation for Max-IP. 2. 2^{O(log* n)}-dimensional Hardness for Exact Max-IP Over The Integers. Last, we revisit the hardness of solving Max-IP exactly for vectors with integer entries. We show that, under SETH, for Max-IP with sets of n vectors from Z^{d} for some d = 2^{O(log* n)}, every exact algorithm requires n^{2 - o(1)} time. With the reduction from [Williams, SODA 2018], it follows that l_2-Furthest Pair and Bichromatic l_2-Closest Pair in 2^{O(log* n)} dimensions require n^{2 - o(1)} time. 3. Connection with NP dot UPP Communication Protocols. Last, We establish a connection between conditional lower bounds for exact Max-IP with integer entries and NP dot UPP communication protocols for Set-Disjointness, parallel to the connection between conditional lower bounds for approximating Max-IP and MA communication protocols for Set-Disjointness. The lower bounds in our first and second results make use of a new MA protocol for Set-Disjointness introduced in [Rubinstein, 2017]. Our algorithms utilize the polynomial method and simple random sampling. Our third result follows from a new dimensionality self reduction from the Orthogonal Vectors problem for n vectors from {0,1}^d to n vectors from Z^l using Chinese Remainder Theorem, where l = 2^{O(log* d)}, dramatically improving the previous reduction in [Williams, SODA 2018]. As a side product, we obtain an MA communication protocol for Set-Disjointness with complexity O(sqrt{nlog n loglog n}), slightly improving the O(sqrt(n) log n) bound [Aaronson and Wigderson, TOCT 2009], and approaching the Omega(sqrt{n}) lower bound [Klauck, CCC 2003].Moreover, we show that (under SETH) one can apply the sqrt(n) BQP communication protocol for Set-Disjointness to prove near-optimal hardness for approximation to Max-IP with vectors in {-1,1}^d. This answers a question from [Abboud et al., FOCS 2017] in the affirmative. 32-G575

May 17

Improved Bounds for Perfect Hashing

Venkat Guruswami
Carnegie Mellon University (CMU)

Part Of

4:30P
- 5:30P

Location

32-G575
Add to Calendar 2018-05-17 16:30:00 2018-05-17 17:30:00 America/New_York Improved Bounds for Perfect Hashing Abstract: A code C over alphabet {1,2,...,k} of length n is said to be a k-hash code if every k distinct elements of C have a coordinate where they all differ. Understanding the largest possible rate (in bits), defined as (log_2 |C|)/n, of a k-hash code is a classical problem. It arises in two equivalent contexts: (i) the smallest size possible for a perfect hash family that maps a universe of prescribed size into {1,2,...,k}, and (ii) the zero-error capacity for decoding with lists of size less than k for a certain combinatorial channel.A general upper bound of k!/k^{k-1} on the rate of a k-hash code (in the limit of large n) was obtained by Fredman and Komlos in 1984 for any k \ge 4. Arikan (1994) improved the bound for k=4 (from 0.375) to 0.3512. For k > 4, however, the original Fredman-Komlos bound has remained the best known. In this talk, I’ll describe two recent works making progress on these bounds. The first (joint with Marco Dalai and Jaikumar Radhakrishnan) improves the rate upper bound to 6/19 < 0.3158 for k=4. The second (with Andrii Riazanov) gives the first improvement over the Fredman-Komlos bound for every k \ge 5.Our approach is based on a careful combination of the Plotkin-type bounds in coding theory and Hansel's lemma for covering the complete graph by bipartite graphs. 32-G575

May 16

Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy

Lisa Yang

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2018-05-16 16:00:00 2018-05-16 17:00:00 America/New_York Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Abstract: Non-signaling games are an important object of study in the theory of computation, both for their role in quantum information and for (classical) cryptography. In this work, we study the behavior of these games under parallel repetition.We show that, unlike the situation both for k-player classical games (for k >= 3) and for two-player non-signaling games, there are k-player non-signaling games whose values do not tend to 0 with sufficient parallel repetition.We show that in general:Every game's non-signaling value under parallel repetition either is lower bounded by a positive constant or decreases exponentially with the number of repetitions.Exponential decrease occurs if and only if the game's "sub-non-signaling value" (Lancien and Winter, CJTCS '16) is less than 1.We also analyze a specific 3k-player game (for every k >= 1), and show that its non-signaling value remains exactly (2/3)^k under any number of parallel repetitions.?Joint work with Justin Holmgren.? 32-G575

May 09

Learning Mixtures of Product Distributions via Higher Multilinear Moments

Sitan Chen
MIT

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2018-05-09 16:00:00 2018-05-09 17:00:00 America/New_York Learning Mixtures of Product Distributions via Higher Multilinear Moments Abstract: Learning mixtures of k binary product distributions is a central problem in computational learning theory, but one where there are wide gaps between the best known algorithms and lower bounds (even for restricted families of algorithms). We narrow many of these gaps by developing novel insights about how to reason about higher order multilinear moments. Our results include: 1) an n^{O(k^2)} time algorithm for learning mixtures of binary product distributions, giving the first improvement on the n^{O(k^3)} time algorithm of Feldman, O'Donnell and Servedio (FOCS '05), 2) an n^{\Omega(\sqrt{k})} statistical query lower bound, improving on the quasipolynomial lower bound that is based on connections to sparse parity with noise, and 3) a quasipolynomial time algorithm for learning mixtures of $k$ subcubes. This special case can still simulate many other hard learning problems, but is much richer than any of them alone. As a corollary, we obtain more flexible algorithms for learning decision trees under the uniform distribution, that work with stochastic transitions, when we are only given positive examples and with a polylogarithmic number of samples for any fixed k.Joint work with Ankur Moitra. 32-G575

April 25

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

Manuel Sabin
UC Berkeley

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2018-04-25 16:00:00 2018-04-25 17:00:00 America/New_York Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity Abstract: We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors requires $n^{k - o(1)}$ time or k-CLIQUE requires $n^{\omega k/3 - o(1)}$ time (for $\omega$ the matrix multiplication constant) to count on randomized machines for all but finitely many input lengths, then the following hold: BPP can be decided in polynomial time using only $n^{\alpha}$ random bits on average over any efficient input distribution, for any constant $\alpha > 0$ BPP can be decided in polynomial time with no randomness on average over the uniform distribution DTIME [t(n)] is not contained in BPP, for time-constructible $t(n)=n^{\omega(1)}$These derandomizations improve over previous ones achieved from worst-case uniform assumptions by succeeding on all but finitely many input lengths, as is wanted in asymptotics. Previously, derandomizations from worst-case uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the k-Orthogonal Vectors and k-CLIQUE problems that makes removing this restriction possible.Via this uniform derandomization, we connect the problem-centric and resource-centric views of complexity theory by showing that exact hardness assumptions made about specific problems like k-CLIQUE imply structural results like EXP is not equal BPP. Viewed pessimistically, this result poses a barrier to proving some of the main assumptions of fine-grained complexity, lest we also attain major breakthroughs in classical complexity theory. Alternately, we can hope to make progress on problems like EXP vs BPP by working on very concrete conjectures about specific problems.Joint with: Marco Carmosino, Russell Impagliazzo 32-G575

March 21

Detecting Correlations with Little Memory and Communication

Yuval Dagan
Technion

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2018-03-21 16:00:00 2018-03-21 17:00:00 America/New_York Detecting Correlations with Little Memory and Communication Abstract: 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. We prove a tight trade-off between the memory/communication complexity and the sample complexity, implying (for example) that to detect pairwise correlations with optimal sample complexity, the number of required memory/communication bits is at least quadratic in the dimension. Our results substantially improve those of Shamir (2014), which studied a similar question in a much more restricted setting. To the best of our knowledge, these are the first provable sample/memory/communication trade-offs for a practical estimation problem, using standard distributions, and in the natural regime where the memory/communication budget is larger than the size of a single data point. To derive our theorems, we prove a new information-theoretic result, which may be relevant for studying other information-constrained learning problems. Joint work with Ohad Shamir. 32-G575

February 15

Parity samplers and explicit, epsilon-balanced codes close to the GV Bound

Amnon Ta-Shma
Tel-Aviv University

Part Of

10:00A
- 11:30A

Location

32-D463 STAR
Add to Calendar 2018-02-15 10:00:00 2018-02-15 11:30:00 America/New_York Parity samplers and explicit, epsilon-balanced codes close to the GV Bound Abstract: I will show an explicit construction of a binary error correcting code with relative distance 1/2-epsilon and relative rate about epsilon^2. This comes close to the Gilbert-Varshamov bound and theLP lower bound. Previous explicit constructions had rate aboutepsilon^3, and this is the first explicit construction to get that close to the Gilbert-Varshamov bound.Technically, we define Parity Samplers. A parity sampler is a collection of setswith the propertythat for every "test"A of a given constant density, the probability a setfrom the collection falls into the test set A an\emph{even} number of times is about half. A\emph{sparse} parity sampler immediately implies a good code with distance close to half. The completet-complex of all sequences of cardinalityt is a good parity sampler, but with too many sets in the collection.Rozenman andWigderson, and independentlyAlon, used random walks over expanders to explicitly construct sparse parity samplers, and their construction implies explicit codes with relative rateepsilon^4.I will show how one can get better explicit parity samplers (and therefore also better explicit codes) using a variant of thezig-zag product. In the random walk sampler, there exist many sets with substantial overlap. One way to look at thezig-zag product is that it takes a sub-collection of the random walk sampler, and this sub-collection has a smaller overlap between sets in the collection. Thezig-zag product achieves that by keeping a small internal state. I will show that by enlarging the internal state one can further reduce the overlap, and as a result improve the quality of the parity sampler.This talk will serve as follow-up to the talk given at the TOC Seminar on Tuesday, February 13th. 32-D463 STAR

January 17

Fault Tolerant Data Structures

Keerti Choudhary
Weizmann Institute

Part Of

4:00P
- 5:00P

Location

Seminar Room G575
Add to Calendar 2018-01-17 16:00:00 2018-01-17 17:00:00 America/New_York Fault Tolerant Data Structures Abstract:In this talk, we look at the problem of single-source-reachability (SSR) in presence of failures of vertices and edges. In the static setting, it can be solved in O(|V|+|E|) time, for any directed graph G=(V, E). To model the scenario of a faulty network, we associate a parameter k with the network such that there are at most k vertices (or edges) that are failed at any stage. The goal is to preprocess the graph G and compute a compact data structure, that, given any set F of at most k vertices (or edges), efficiently solves the SSR problem for the graph G\F. We show that for any set F of size k, solves SSR problem for G\F in O(2^k n) time. Previously the only known construction was single fault. One major application of this structure is a fault tolerant algorithm for SSC (strongly connected components). Seminar Room G575

November 30

Mixture Models, Robustness, and Sum of Squares Proofs

Jerry Li
MIT

Part Of

4:00P
- 5:00P

Location

Seminar Room G449 (Patil/Kiva)
Add to Calendar 2017-11-30 16:00:00 2017-11-30 17:00:00 America/New_York Mixture Models, Robustness, and Sum of Squares Proofs Abstract. We use the Sum of Squares (SoS) method to develop a new efficient algorithm for clustering and mean estimation in well-separated high-dimensional mixture models, substantially improving upon the statistical guarantees achieved by previous efficient algorithms.In particular, we study mixtures of k distributions, where every pair of distributions has means separated by separated byat least k^epsilon for any epsilon > 0. In the special case of spherical Gaussian mixtures, we give a k^O(1/epsilon^2)-time algorithm that learns the means of the components in the mixture and accurately clusters samples from the mixture.This is the first algorithm to improve on greedy (“single-linkage”) and spectral clustering, breaking a long-standing barrier for efficient algorithms at separation k^1/4.Our techniques are based on adapting algorithmic ideas from robust statistics, and are potentially of independent interest. Our main algorithm for learning mixture models provides an entirely SoS interpretation of the convex programming framework of [Diakonikolas et al, FOCS 16]. We show that many of the proofs from that paper can be replaced with much simpler proofs using only basic concentration and Holder's inequality, which allows us to approach this problem via SoS.As a corollary of this, we also obtain improved rates for robust mean estimation in certain regimes.Joint work with Sam Hopkins, Cornell Seminar Room G449 (Patil/Kiva)

November 29

Matchings in MPC frameworks

Slobodan Mitrovic
EPFL

Part Of

4:00P
- 5:00P

Location

Seminar Room G575
Add to Calendar 2017-11-29 16:00:00 2017-11-29 17:00:00 America/New_York Matchings in MPC frameworks Abstract. The last decade has witnessed the success of a number of \emph{massive parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. These frameworks allow for much more local computation, compared to the classical PRAM models. In this context, we investigate the complexity of one of the most fundamental graph problems: \emph{Maximum Matching}. We show that if the memory per machine is $\Omega(n)$ (or even only $n/(\log n)^{O(\log \log n)}$), then for any fixed constant $\eps > 0$, one can compute a $(2+\eps)$-approximation to Maximum Matching in $O\left((\log \log n)^2\right)$ MPC rounds. This constitutes an exponential improvement over previous work -- both the one designed specifically for MPC and the one obtained via connections to PRAM or distributed algorithms -- which required $\Theta(\log n)$ rounds to achieve similar approximation guarantees.To establish our result we need to deviate from the previous work in two important ways. Firstly, we use \emph{vertex--based} graph partitioning, instead of the edge--based approaches that were utilized so far. Secondly, we develop a technique of \emph{round compression}. This technique enables one to take a (distributed) algorithm that computes an $O(1)$-approximation of maximum matching in $O(\log n)$ \emph{independent} PRAM phases and implement a super-constant many of these phases in only a constant number of actual MPC rounds. These techniques turn out to be what one needs to truly take advantage of the MPC model, as compared to the PRAM model, even in the regime of (sub-)linear memory per machine.Based on joint work with Artur Czumaj, Jakub ??cki, Aleksander M?dry, Krzysztof Onak and Piotr Sankowski. [https://arxiv.org/abs/1707.03478] Seminar Room G575

November 16

Jiantao Jiao: Instance-optimal learning of the total variation distance

Jiantao Jiao
Stanford

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-11-16 16:00:00 2017-11-16 17:00:00 America/New_York Jiantao Jiao: Instance-optimal learning of the total variation distance Title: Instance-optimal learning of the total variation distanceAbstract: The total variation distance (statistical distance) plays fundamental roles in statistics, machine learning, and theoretical computer science. We consider the problem of learning the total variation distance between $p$ and $q$ for any fixed $q$ given independent identically distributed samples from $p$. We characterize the optimal sample complexity in terms of $q$ and $\epsilon$, and construct a near-linear time algorithm that achieves the optimal sample complexity for each $q$. In other words, the learner we constructed is instance optimal, paralleling the work of VV'14 on instance optimal identity testing. The dependence on $q$ in learning the total variation distance is drastically different from that in testing identity. We show that for any fixed $q$, the performance of the optimal learner with $n$ samples is essentially that of the plug-in approach with $n \log n$ samples, where the plug-in approach evaluates the total variation distance between the empirical distribution of $p$ and the known distribution $q$. The key methodology behind our achievability and lower bound constructions is the idea of local approximation, which bridges approximation theory and concentration inequalities. In particular, the upper and lower bounds are dual to each other, and proofs of upper bounds can be translated into proofs of lower bounds. We generalize the local approximation approach to learning the total variation distance when both $p$ and $q$ are unknown. We obtain tight upper and lower bounds of the optimal sample complexity including the dependence on $\epsilon$, where we show it is necessary to utilize multivariate polynomial approximation: any univariate polynomial approximation scheme fails to achieves the optimal sample complexity. We show that the sample complexity for the both $p,q$ unknown case is essentially the same as the $q$ known case with $q$ being uniform, showing that $q$ being uniform is the most difficult case. If time permits, we discuss the potential applications of the general local approximation methodology, which has proved to produce the optimal learners in a variety of settings such as learning the entropy, power sum functional, KL divergence, Hellinger divergence, $\chi^2$ divergence, support size, etc. Based on joint work with Yanjun Han and Tsachy Weissman. (https://arxiv.org/abs/1705.00807) 32-G575

November 02

Fooling intersections of low-weight halfspaces

Li-Yang Tan
TTI Chicago

Part Of

4:00P
- 5:00P

Location

Seminar Room G882 (Hewlett Room)
Add to Calendar 2017-11-02 16:00:00 2017-11-02 17:00:00 America/New_York Fooling intersections of low-weight halfspaces 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 givean explicit pseudorandom generator that $\delta$-fools any intersection of $k$weight-$t$ halfspaces with seed length $\poly(\log n, \log k,t,1/\delta)$. Inparticular, our result gives an explicit PRG that fools any intersection of any$\mathrm{quasipoly}(n)$ number of halfspaces of any $\mathrm{polylog}(n)$ weight to any$1/\mathrm{polylog}(n)$ accuracy using seed length $\mathrm{polylog}(n)$. Prior to this workno explicit PRG with non-trivial seed length was known even for foolingintersections of $n$ weight-$1$ halfspaces to constant accuracy.The analysis of our PRG fuses techniques from two different lines of work onunconditional pseudorandomness for different kinds of Boolean functions. Weextend the approach of Harsha, Klivans, and Meka for foolingintersections of regular halfspaces, and combine this approach with results ofBazzi and Razborov on bounded independencefooling CNF formulas. Our analysis introduces new coupling-based ingredientsinto the standard Lindeberg method for establishing quantitative central limittheorems and associated pseudorandomness results.Joint work with Rocco Servedio. Seminar Room G882 (Hewlett Room)

November 01

Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo

Andrej Risteski
MIT

Part Of

4:00P
- 5:00P

Location

Seminar Room G575
Add to Calendar 2017-11-01 16:00:00 2017-11-01 17:00:00 America/New_York Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo A key task in Bayesian statistics is sampling from distributions that are only specified up to a partition function (i.e., constant of proportionality). However, without any assumptions, sampling (even approximately) can be #P-hard, and few works have provided "beyond worst-case" guarantees for such settings. For log-concave distributions, classical results going back to Bakry and Emery (1985) show that natural continuous-time Markov chains called Langevin diffusions mix in polynomial time. The most salient feature of log-concavity violated in practice is uni-modality: commonly, the distributions we wish to sample from are multi-modal. In the presence of multiple deep and well-separated modes, Langevin diffusion suffers from torpid mixing. We address this problem by combining Langevin diffusion with simulated tempering. The result is a Markov chain that mixes more rapidly by transitioning between different temperatures of the distribution. We analyze this Markov chain for the canonical multi-modal distribution: a mixture of gaussians (of equal variance). The algorithm based on our Markov chain provably samples from distributions that are close to mixtures of gaussians, given access to the gradient of the log-pdf. For the analysis, we use a spectral decomposition theorem for graphs (Gharan and Trevisan, 2014) and a Markov chain decomposition technique (Madras and Randall, 2002).Joint work with Rong Ge and Holden Lee. Seminar Room G575

October 25

Non-Interactive Agreement & Dimension Reduction for Polynomials

Pritish Kamath
MIT

Part Of

4:30P
- 5:30P

Location

Seminar Room G575
Add to Calendar 2017-10-25 16:30:00 2017-10-25 17:30:00 America/New_York Non-Interactive Agreement & Dimension Reduction for Polynomials Title: Non-Interactive Agreement & Dimension Reduction for PolynomialsAbstract: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, ... , Y_n) respectively where {(X_i, Y_i)} are drawn i.i.d. from P(x,y). Both players look at their share of randomness, and output an element of [k]. Their goal is to maximize the probability that their outputs are the same, while ensuring that their outputs are marginally uniform.Given P(x,y) and k, what is the largest correlation (or agreement probability) that the players can achieve? In the special case where P(x,y) is the distribution of \rho-correlated Gaussians, the largest achievable correlation is also known as the "Optimal Noise-Stability of a k-partition" and has received wide interest in Computer Science. More generally, it is also related to the notions of common information studied in Information Theory.It turns out that this value is not well understood, even in the special case of correlated Gaussians! Moreover, this value is a priori not even "computable", as there is no immediate upper bound on the number of samples the players need to draw in order to achieve the best possible correlation!In this work, we obtain explicit (computable) bounds on the number of samples needed to get \epsilon-close to the maximum achievable correlation (or even for the more general problem of "non-interactive simulation"). This implies computability of the maximum achievable correlation. [Our bounds significantly improve upon the results obtained recently by De, Mossel & Neeman, using fundamentally different techniques.]At the heart of our result is a new technique that we call "Dimension Reduction for Polynomials". It is analogous to the Johnson-Lindenstrauss lemma, which is a dimension reduction for vectors. This technique is mostly elementary, and we believe it to be of independent interest.This talk will discuss the motivational aspects of the problem, its moral and technical connections to other problems in computer science and will mainly focus on the new technique of "dimension reduction for polynomials".Based on joint works with Badih Ghazi, Prasad Raghavendra and Madhu Sudan.https://eccc.weizmann.ac.il/report/2016/104/https://eccc.weizmann.ac.il/report/2017/125/ Seminar Room G575

October 11

On The Power of Statistical Zero Knowledge

Lijie Chen
MIT

Part Of

4:00P
- 5:00P

Location

Seminar Room G575
Add to Calendar 2017-10-11 16:00:00 2017-10-11 17:00:00 America/New_York On The Power of Statistical Zero Knowledge We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZK contains hard problems, by exhibiting an oracle relative to which SZK (indeed, even NISZK) is not contained in the class UPP, containing those problems solvable by randomized algorithms with unbounded error. This answers an open question of Watrous from 2002 [Aar]. Second, we “lift” this oracle separation to the setting of communication complexity, thereby answering a question of Goos et al. (ICALP 2016). Third, we give relativized evidence that perfect zero knowledge proofs (captured by the class PZK) are weaker than general zero knowledge proofs. Specifically, we exhibit oracles relative to which SZK does not belong to PZK, NISZK does not belong to NIPZK, and PZK is not equal to coPZK. The first of these results answers a question raised in 1991 by Aiello and Hastad (Information and Computation), and the second answers a question of Lovett and Zhang (2016). We also describe additional applications of these results outside of structural complexity. The technical core of our results is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree.Joint work with Adam Bouland, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan. Seminar Room G575

September 28

Trading Information Complexity for Error

Yuval Dagan
Technion

Part Of

3:00P
- 4:00P

Location

Seminar Room G575
Add to Calendar 2017-09-28 15:00:00 2017-09-28 16:00:00 America/New_York Trading Information Complexity for Error Abstract: 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 the epsilon-error randomized communication complexity of set disjointness is n[C_DISJ - Theta(h(epsilon))] + o(n), where C_DISJ ? 0.4827 is the constant of set disjointness found by Braverman et al.Joint work with Yuval Filmus, Hamed Hatami and Yaqiao Li. Seminar Room G575

September 27

Paul Hand: Deep Compressed Sensing

Paul Hand
Rice University

Part Of

4:00P
- 5:00P

Location

32-D463 (Star)
Add to Calendar 2017-09-27 16:00:00 2017-09-27 17:00:00 America/New_York Paul Hand: Deep Compressed Sensing Abstract: 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. As deep generative priors (such as those obtained via generative adversarial training) improve, analogous improvements in the performance of compressed sensing and other inverse problems may be realized across the imaging sciences. In joint work with Vladislav Voroninski, we provide a theoretical framework for studying inverse problems subject to deep generative priors. In particular, we prove that with high probability, the non-convex empirical risk objective for enforcing random deep generative priors subject to compressive random linear observations of the last layer of the generator has no spurious local minima, and that for a fixed network depth, these guarantees hold at order-optimal sample complexity. 32-D463 (Star)

September 06

An approach for 2-to-1 Games Conjecture via expansion on the Grassmann Graph

Dor Minzer
Tel-Aviv University

Part Of

4:00P
- 5:00P

Location

32-G575
Add to Calendar 2017-09-06 16:00:00 2017-09-06 17:00:00 America/New_York An approach for 2-to-1 Games Conjecture via expansion on the Grassmann Graph Abstract: The PCP theorem characterizes the computational class NP, so as to allow proving approximation problems are NP-hard.One of the fundamental open questions in PCP theory is whether a special type of PCP, namely 2-to-1 Games, is still NP-hard. This conjecture is a variant of Khot's well-known Unique Games conjecture.A recent line of study suggests a new attack on the 2-to-1 games conjecture (albeit with imperfect completeness). This approach is based on a mathematical object called the Grassmann Graph, and relies on an unproven combinatorial hypothesis on it. This, in turn, leads to the study of edge expansion in this graph. More specifically, to the study of sets of vertices in the Grassmann Graph, whose edge expansion is not optimal. It turns out that the study of the combinatorial hypothesis is in fact equivalent to the study of edge expansion (Barak Kothari). Thus extending these results would complete the approach, proving that distinguishing between 2-to-1 games with close to 1 value, and 2-to-1 games with arbitrarily small value, is NP-hard.This talk discusses this line of study. Based on joint works with Irit Dinur, Subhash Khot, Guy Kindler and Muli Safra. 32-G575