TCS+

Our next talk will take place this coming Wednesday, October 7th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). David Zuckerman from the University of Texas at Austin will speak about his breakthrough work with Eshan Chattopadhyay constructing “Explicit Two-Source Extractors and Resilient Functions” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, please see the website.

We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}. The best previous extractor, by Bourgain, required each source to have min-entropy .499n.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently, and the remaining q=n^{1-\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1/2 – \delta}.

Our explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.

Joint work with Eshan Chattopadhyay

Our next talk — the first of the season!— will take place this coming Wednesday, September 30th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Mika Göös from University of Toronto will speak about “Communication Complexity vs. Partition Numbers,” an exciting work to appear at FOCS’15 (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, please see the website.

In communication complexity, perhaps the most basic observation is that a deterministic protocol computing a function partitions the communication matrix of into monochromatic rectangles, where is the number of bits exchanged between Alice and Bob. In other words, the logarithm of the partition number (least number of monochromatic rectangles needed to partition the communication matrix) is a lower bound on communication complexity.

We show that deterministic communication complexity can be superlogarithmic in the partition number. We also obtain near-optimal deterministic lower bounds for the related Clique vs. Independent Set problem (CIS; introduced by Yannakakis in 1988) that captures a one-sided variant of the partition number. In particular, this yields new lower bounds for the log-rank conjecture. We also provide some co-nondeterministic lower bounds for CIS, which has applications to the Alon–Saks–Seymour conjecture in graph theory.

To obtain the above results, we cheat: we study analogous questions in the easy-to-understand world of decision tree complexity, and then we “lift” these results over to communication complexity using a general simulation theorem.

Joint work with Toniann Pitassi and Thomas Watson. To appear at FOCS’15.

Fall is coming, and with it, a new season of TCS+! Every other Wednesday, you’ll be able to tune in for a variety of talks and exciting results — keeping on with the long established 2-year-old tradition of our online seminar:

TCS+, a series of online seminars in theoretical computer science, will solve all your worries. The seminars are run using the “hangout” feature of Google+. The speaker and slides are broadcast live, as well as recorded and made available online. Anyone with a computer (and a modern browser) can watch, and anyone with a webcam can join the live audience and participate. The goal is to make engaging talks accessible to the widest possible audience, thereby ensuring a carbon-free dissemination of ideas across the globe.

As a new feature, you can already suggest talks and speakers for the series by visiting our website: tell us what you want to hear!

Our first talk will take place on September 30th, at 1pm EDT: Mika Göös will be speaking on “Communication Complexity vs. Partition Numbers.” As usual, groups (and individuals) can sign up for a seat in the Hangout — allowing live interaction with the speaker — via our online form. A link to join the Hangout will then be sent to the participants the day of the talk (the video will also be available on YouTube, both streaming and after the talk.)

Next talks will feature David Zuckerman (Oct 7), Ryan O’Donnell (Oct 14), and Li-Yang Tan (Oct 28). The up-to-date schedule and details can be found on the TCS+ website.

Hoping to see you on Sept 30th — and all throughout the season!

On Wednesday, June 10th at 1 PM Eastern Time (10 AM Pacific Time, 7 PM Central European Time, 5 PM UTC), Aaron Roth will talk about “Correctness Protection via Differential Privacy” (abstract below).

Please sign up on the online form if you wish to join the talk as a group.

For more information about the TCS+ online seminar series, please see the website.

False discovery is a growing problem in scientific research. Despite sophisticated statistical techniques for controlling the false discovery rate and related statistics designed to protect against spurious discoveries, there is significant evidence that many published scientific papers contain incorrect conclusions.

In this talk we consider the role that adaptivity has in this problem. A fundamental disconnect between the theorems that control false discovery rate and the practice of science is that the theorems assume a fixed collection of hypotheses to be tested, selected non-adaptively before the data is gathered, whereas science is by definition an adaptive process, in which data is shared and re-used, while hypotheses are generated after seeing the results of previous tests.

We note that false discovery cannot be prevented when a substantial number of adaptive queries are made to the data, and data is used naively — i.e. when queries are answered exactly with their empirical estimates on a given finite data set. However we show that remarkably, there is a different way to evaluate statistical queries on a data set that allows even an adaptive analyst to make exponentially many queries to the data set, while guaranteeing that with high probability, all of the conclusions he draws generalize to the underlying distribution. This technique counter-intuitively involves actively perturbing the answers given to the data analyst, using techniques developed for privacy preservation — but in our application, the perturbations are added entirely to increase the utility of the data.

Joint work with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, and Omer Reingold.

On Wednesday, May 27th at 1 PM Eastern Time (10 AM Pacific Time, 7 PM Central European Time, 5 PM UTC), Aaron Potechin will talk about “Sum of Squares Lower Bounds for the Planted Clique Problem” (abstract below).

Please sign up on the online form if you wish to join the talk as a group.

For more information about the TCS+ online seminar series, please see the website.

The planted clique problem asks whether or not we can find a -clique which is planted in a random graph. Although the expected size of the largest clique in a random graph is only , we currently do not know of any polynomial time algorithm which can find a planted clique of size much smaller than .

The sum of squares hierarchy gives a hierarchy of approximation algorithms, each more powerful than the last. These algorithms are some of the most powerful approximation algorithms we know of, but their performance on many problems is not well understood.

In this talk, I will present the first non-trivial bounds on the performance of the sum of squares hierarchy on the planted clique problem, describing the planted clique problem, the sum of squares hierarchy, and how we can show that the sum of squares hierarchy fails to find the planted clique if its size is sufficiently small.

On Wednesday, May 13th at 1 PM Eastern Time (10 AM Pacific Time, 7 PM Central European Time, 5 PM UTC), Ilias Diakonikolas will talk about “Efficient Distribution Estimation via Piecewise Polynomial Approximation” (abstract below).

Please sign up on the online form if you wish to join the talk as a group.

For more information about the TCS+ online seminar series, please see the website.

In this talk, we will focus on a core problem in unsupervised learning: how to infer information about a distribution based on random samples. We will describe a framework that yields new, provably efficient estimators for several natural and well-studied distribution families, including mixtures of structured distribution families (e.g., gaussian, log-concave, etc.).
The key tool that enables our approach is a new algorithm for learning probability distributions that are well approximated by piecewise polynomial density functions. Let be the density function of an arbitrary univariate distribution, and suppose that is close in distance to an unknown piecewise polynomial function with $t$ interval pieces and degree . Our algorithm draws samples from , runs in time and with probability at least outputs an -piecewise degree- hypothesis that is close to .
Our general algorithm yields (near-)sample-optimal and near-linear time estimators for a wide range of structured distribution families
over both continuous and discrete domains in a unified way. For most of our applications, these are the first sample-optimal and near-linear time estimators in the literature. Moreover, we experimentally demonstrate that our algorithm performs very well in practice.

The talk will be based on separate joint works with S. Chan, R. Servedio, X. Sun (STOC’14); and more recent work with J. Acharya, J. Li, L. Schmidt.

On Wednesday, April 29th at 1 PM Eastern Time (10 AM Pacific Time, 7 PM Central European Time, 5 PM UTC), Muli Safra will talk on “Monotonicity Testing and Boolean Isoperimetric type Theorems” (abstract below).

Please sign up on the online form if you wish to join the talk as a group.

For more information about the TCS+ online seminar series, please see the website.

We show a directed and robust analogue of a Boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes non-adaptive queries to a function , always accepts a monotone function and rejects a function that is -far from being monotone with constant probability.

Joint work with Subhash Khot and Dor Minzer. (Paper available on ECCC.)

On Wednesday, April 15th at 1 PM Eastern Time (10 AM Pacific Time, 7 PM Central European Time, 5 PM UTC), Shayan Oveis Gharan will talk about “Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP” (abstract below).

Please sign up on the online form if you wish to join the talk as a group.

For more information about the TCS+ online seminar series, please see the website.

We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n). We prove this by showing that any k-edge-connected unweighted graph with k≥7log(n) has a polylog(k)/k-thin spanning tree.
Our main new ingredient is a procedure, albeit an exponentially sized convex program, that “transforms” graphs that do not admit any spectrally thin trees into those that provably have spectrally thin trees. More precisely, given a k-edge-connected graph G=(V,E) where k≥7log(n), we show that there is a matrix D that “preserves” the structure of all cuts of G such that for a set F⊆E that induces an Ω(k)-connected graph, the effective resistance of every edge in F w.r.t. D is at most O(polylog(k)/k). Then, we use a recent extension of the seminal work of Marcus, Spielman and Srivastava [MSS13] by the authors [AO14b] to prove the existence of an O(polylog(k)/k)-spectrally thin tree with respect to D. Such a tree is O(polylog(k)/k)-combinatorially thin with respect to G as D preserves the structure of cuts of G.

Joint work with  Nima Anari.

On Wednesday, April 1st at 1 PM Eastern Time (10 AM Pacific Time, 7 PM Central European Time, 5 PM UTC), Shachar Lovett will talk about “Structure and Pseudo-Randomness in Coding Theory” (abstract below).

Please sign up on the online form if you wish to join the talk as a group.

For more information about the TCS+ online seminar series, please see the website.

The theory of structure and pseudo-randomness has been very influential in several areas of mathematics, such as number theory, graph theory and harmonic analysis. It is also been influential in theoretical computer science, with applications in complexity theory, cryptography and property testing. At a high level, it allows to analyze arbitrary objects by decomposing them to a “structural” component and a “pseudo-random” component. The pseudo-random component behaves in many senses like random noise, while the structural component has a concise representation which makes it amenable to analysis and algorithmic manipulation.

In this talk, I will describe applications of this paradigm to coding theory. I will describe a new general approach to list decoding, which follows by decomposing an arbitrary received word to a structural received word and pseudo-random noise. This allows for a simplified analysis of the list decoding problem. In particular, I will describe how this approach leads to a resolution of a conjecture by Gopalan, Klivans and Zuckerman [STOC 2008], that the list decoding radius of Reed-Muller codes (in certain regimes) is equal to the minimal distance of the code.

Based on joint works with Abhishek Bhowmick.

PS: For those viewers that watch us from Europe, please notice the daylight saving times change will occur the week-end prior to the talk.

On Wednesday, March 18th at 1 PM Eastern Time (10 AM Pacific Time, 6 PM Central European Time, 5 PM UTC), Shai Halevi will talk about “Cryptographic Graded-Encoding Schemes: Recent Developments” (abstract below).

Please sign up on the online form if you wish to join the talk as a group.

For more information about the TCS+ online seminar series, please see the website.

Graded-encoding schemes are an extremely powerful tool in our crypto toolbox. Introduced two years ago by Garg, Gentry, and Halevi (as an approximation of multilinear maps), they were used to realize such “impossible goals” as general-purpose obfuscation, functional encryption, witness encryption, and more. However so far we have very few candidate  constructions of graded encoding schemes, all based on similar principles, and the security of these candidates is poorly understood.Recently, Cheon, Han, Lee, Ryu, and Stehle developed a powerful line of attacks on the existing candidate constructions (extending early attacks of Garg, Gentry, and Halevi), and showed how to break many of the hardness assumptions that were made about these schemes. These attacks were further developed by Gentry et al. and Coron et al., extending them to even wider settings and adapting them to defeat some attempted counter-measures.In this talk I will survey the existing constructions and attacks, and try to describe our current view of the security landscape for these constructions.