TCS+

Our next talk will take place on Wednesday, November 9th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Bo Waggoner (U. Penn) will tell us about joint work with Yiling Chen from FOCS’16 on “Informational Substitutes”  (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, or to suggest a possible topic or speaker, please see the website.

 When can pieces of information be termed substitutes or complements? I’ll propose an answer based on “value of information” theory and show that these definitions are fundamental to some problems both in game theory and algorithms. The “main result” shows that substitutes characterize good “efficient market hypothesis” equilibria in prediction markets; another shows that substitutes characterize efficient approximation algorithms for information acquisition.

The goal is to have a tutorial feel, introducing some fun concepts and tools that are less familiar to theory audiences. It will be heavy on concepts and definitions, light on technicalities.

Our next talk will take place on Wednesday, October 26th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Claire Mathieu (ENS Paris) will tell us about her work “Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics” from FOCS’16 (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, or to suggest a possible topic or speaker, please see the website.

We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs; (2) k-median and k-means in edge-weighted planar graphs; (3) k-means in Euclidean spaces of bounded dimension. Our first and second results extend to minor-closed families of graphs. All our results extend to cost functions that are the p-th power of the shortest-path distance. The algorithm is local search where the local neighborhood of a solution S consists of all solutions obtained from S by removing and adding 1/ϵO(1) centers.

Joint work with Vincent Cohen-Addad and Philip N. Klein.

Our next talk will take place on Wednesday, October 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Ronen Eldan (Weizmann Institute) will tell us about “Kernel-based methods for Bandit Convex Optimization” (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, or to suggest a possible topic or speaker, please see the website.

I will present the first poly-time and -regret algorithm for bandit convex optimization.

Given a convex body , the problem can be described as the following sequential game: at each time step , a player selects an action , and simultaneously an adversary selects a convex loss function . The player’s feedback is its suffered loss, . The player has access to external randomness, and can select her action based on the history . The player’s perfomance at the end of the game is measured through the regret ,
which compares her cumulative loss to the smallest cumulative loss she could have obtained had she known the sequence of loss functions.

Joint w. Sebastien Bubeck and Yin-Tat Lee.

Our next talk will take place on Wednesday, September 28th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Swastik Kopparty (Rutgers University) will tell us about “High rate locally-correctable codes and locally-testable codes with subpolynomial query complexity” (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, or to suggest a possible topic or speaker, please see the website.

Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are error-correcting codes which admit sublinear-time error correcting/detecting algorithms. They have interesting connections to complexity theory, cryptography and classical coding theory. In recent years, a number of different LCCs and LTCs with constant rate and distance were discovered, and in all cases the local correcting/testing algorithms had arbitrary polynomially small query complexity.

I will talk about a recent result showing the existence of codes with constant rate and constant distance which are locally-correctable and locally-testable with subpolynomial query complexity. The key new ingredient (in the context of local correction/testing) is an expander-based distance amplification method of Alon, Edmonds and Luby.

Joint work with Or Meir, Noga Ron-Zewi and Shubhangi Saraf

We’re excited to start a new year of TCS+ talks! Our first talk this Fall will take place this coming Wednesday, September 14th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). We’re honored to have Sushant Sachdeva from Google as our first speaker. Sushant will talk about beautiful work with Kyng, to appear in the upcoming FOCS, giving an elegant algorithm for “Fast Approximate Gaussian Elimination for Laplacians” (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, or to suggest a possible topic or speaker, please see the website.

Solving systems of linear equations in graph Laplacians is a fundamental primitive in scientific computing. Starting with the seminal work of Spielman-Teng that gave the first nearly-linear time algorithm for solving Laplacian systems, there has been a long line of work giving faster Laplacian solvers. These solvers have had a large impact on the design of fast graph algorithms.

In this talk, I’ll present a very simple, nearly-linear time Laplacian solver that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders. Our solver builds a sparse Cholesky factorization for Laplacians — the symmetric version of Gaussian elimination. More precisely, it approximates a Laplacian L as U’U, where U is a sparse upper triangular matrix. Since triangular matrices are easy to invert, this immediately implies a fast Laplacian solver via iterative refinement. The analysis is based on concentration of matrix martingales.

This is joint work with Rasmus Kyng, and will appear at the upcoming FOCS.

Our next talk — the last of the season! — will take place on Wednesday, May 25th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Eric Blais (University of Waterloo) will tell us about the latest development on monotonicity testing of Boolean functions, namely “A Polynomial Lower Bound for Testing Monotonicity” (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, or to suggest a possible topic or speaker, please see the website.

One of the earliest and most fundamental problems in property testing is monotonicity testing: how many queries to a Boolean function do we need to distinguish between the case where  is monotone and the one where is far from monotone? Extensive study of this problem has revealed surprising connections to other topics in the analysis of Boolean functions, including directed isoperimetric inequalities and invariance principles for linear threshold functions.
Yet, despite all this effort, until recently there was still an exponential gap between the best upper and lower bounds for the number of queries that general (adaptive) testers need to test monotonicity.

In this talk, we will see how noise sensitivity and Talagrand’s random DNF functions can be used to significantly improve the lower bound for this problem. As a result, we will see that a polynomial number of queries is both sufficient and necessary to test monotonicity. We will also discuss some related results.

Joint work with Alexander Belov.

Our next talk will take place on Wednesday, May 11th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Ankit Garg (Princeton University) will tell us about his work on “Operator scaling and applications to non-commutative rational identity testing“ (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,* or to suggest a possible topic or speaker, please see the website.

Sinkhorn in 1964 studied the problem of matrix scaling, given a non-negative matrix , find diagonal matrices with positive entries (if exist) and s.t. is doubly stochastic. He proved that a natural iterative algorithm finds this scaling if entries of   are strictly positive. Matrix scaling has since found applications in various fields such as statistics, numerical analysis, operations research, combinatorial geometry and approximating the permanent. Gurvits in 2004 found a striking generalization of matrix scaling, called operator scaling, where one wants to “scale” completely positive operators to make them “doubly stochastic.” Gurvits proved that a natural iterative algorithm converges, and, in fact, in polynomial number of iterations in some special cases. We analyze Gurvits’ algorithm completely and prove that it always converges in polynomial number of iterations. Our analysis is simple, providing explicit bounds on the “capacity” measure of completely positive operators introducted by Gurvits. Using this we obtain the first deterministic polynomial time algorithm for computing rank of a symbolic matrix in non-commuting variables. Previous algorithms required exponential time (with or without randomness). This problem (of computing rank of a symbolic matrix) has a rich history and has appeared in various forms in a remarkable number of mathematical and computational areas. Besides non-commutative algebra, it also has various connections to computational complexity and de-randomization, commutative invariant theory and quantum information theory.

This is based on joint work with Leonid Gurvits, Rafael Oliveira and Avi Wigderson.

* Following this talk, our next speaker (and last of the season!) will be Eric Blais, on May 25th, on “A Polynomial Lower Bound for Testing Monotonicity.”

Our next talk will take place on Wednesday, April 27th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Omer Reingold (Samsung Research America) will describe his recent results on “Constant-round Interactive-proofs for Delegating Computation” (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,* or to suggest a possible topic or speaker, please see the website.

Interactive proofs, introduced by Goldwasser, Micali, and Rackoff, have had a dramatic impact on Complexity Theory and Cryptography. In particular, the celebrated Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a large number of communication rounds and heavy computation for generating the proof.

We introduce new interactive proofs that are very efficient in the number of rounds and computation time, that are particularly well suited for delegating bounded-space computations (e.g., in the context of cloud computing). Our main result is that for every statement that can be evaluated in polynomial time and bounded-polynomial space there exists an interactive proof that satisfies the following strict efficiency requirements:

1.  the honest prover runs in polynomial time,
2. the verifier is almost linear time (and under some conditions even sub linear), and
3. the interaction consists of only a constant number of communication rounds. Prior to this work, very little was known about the power of efficient, constant-round interactive proofs.

Joint work with Guy Rothblum and Ron Rothblum.

* Following this talk, our next speaker will be Ankit Garg, on May 11th, who will talk about “A deterministic polynomial time algorithm for non-commutative rational identity testing.”

Our next talk will take place this coming Wednesday, April 13th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Stephen Fenner (University of South Carolina) will tell us about how “Bipartite Perfect Matching is in quasi-NC” (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,* or to suggest a possible topic or speaker, please see the website.

We show that the bipartite perfect matching problem is in quasi-. That is, it has uniform circuits of quasi-polynomial size , and depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.
We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

Joint work with Rohit Gurjar and Thomas Thierauf. (abs/1601.06319)

* Following this talk, our next speaker will be Omer Reingold, on April 27th, who will talk about “Constant-round Interactive-proofs for Delegating Computation.”

Our next talk will take place this coming Wednesday, March 30th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Ran Raz (Weizmann Institute) will speak about his recent result on learning parities, namely “Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning” (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,* or to suggest a possible topic or speaker, please see the website.

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial.

More formally, in the problem of parity learning, an unknown string was chosen uniformly at random. A learner tries to learn from a stream of samples , where each is uniformly distributed over and is the inner product of and , modulo 2. We show that any algorithm for parity learning, that uses less than bits of memory, requires an exponential number of samples.

Previously, there was no non-trivial lower bound on the number of samples needed, for any learning problem, even if the allowed memory size is (where is the space needed to store one sample).

We also give an application of our result in the field of bounded-storage cryptography. We show an encryption scheme that requires a private key of length , as well as time complexity of per encryption/decryption of each bit, and is provenly and unconditionally secure as long as the attacker uses less than memory bits and the scheme is used at most an exponential number of times. Previous works on bounded-storage cryptography assumed that the memory size used by the attacker is at most linear in the time needed for encryption/decryption.

* Following this talk, our next two speakers will be Stephen Fenner (April 13th) and Omer Reingold (April 27th), respectively on “Bipartite Perfect Matching is in quasi-NC” and “Constant-round Interactive-proofs for Delegating Computation.”