TCS+

A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, September 27th — Yuval Peres, Microsoft Research

The next TCS+ talk will take place next Wednesday, September 27th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Yuval Peres (Microsoft Research) will will speak about “Trace reconstruction for the deletion channel” (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.

 

Abstract: In the trace reconstruction problem, an unknown string $x$ of $n$ bits is observed through the deletion channel, which deletes each bit with some constant probability $q$, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconstruct $x$ with high probability?

The best lower bound known is linear in $n$. Until recently, the best upper bound was exponential in the square root of $n$. We improve the square root to a cube root using statistics of individual output bits and some complex analysis; this bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently and concurrently by De, O’Donnell and Servedio). If the string $x$ is random and $q<1/2$, we can show a subpolynomial number of traces suffices by comparison to a biased random walk.

(Joint works with Fedor Nazarov, STOC 2017 and with Alex Zhai, FOCS 2017).

Advertisements

TCS+ talk: Wednesday, June 7 — Erik Waingarten, Columbia University

The next TCS+ talk will take place next Wednesday, June 7th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Erik Waingarten (Columbia University) will will speak about “Settling the query complexity of non-adaptive junta 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.

The problem of testing whether an n-variable function is a k-junta has been one of the main problems in property testing. In this talk, I will show that any non-adaptive algorithm that tests whether an unknown Boolean function f\colon\{0,1\}^n\to\{0,1\} is a k-junta or \varepsilon-far from every k-junta must make \tilde{\Omega}(k^{3/2})/\varepsilon many queries. This result is essentially optimal given Blais’s non-adaptive junta tester, which makes \tilde{O}(k^{3/2})/\varepsilon queries and shows that adaptivity enables polynomial savings in query complexity for junta testing. At a very high level, the proof proceeds by reducing the non-adaptive junta testing of a new class of random Boolean functions to a problem of distinguishing two binomial distributions with a specific kind of noisy query.
This is joint work with Xi Chen, Rocco Servedio, Li-Yang Tan, and Jinyu Xie.

TCS+ talk: Wednesday, May 24 — Mohsen Ghaffari, ETH Zurich

The next TCS+ talk will take place next Wednesday, May 24th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Mohsen Ghaffari (ETH Zurich) will will speak about “On the Complexity of Local Distributed Graph Problems” (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 revisit the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS ’87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and $(\Delta+1)$-vertex coloring), the randomized complexity is at most polylogarithmic in the size $n$ of the network, while the best known deterministic complexity is typically $2^{O(\sqrt{\log n})}$. Understanding and potentially narrowing down this exponential gap is one of the central long-standing open questions in the area of distributed graph algorithms.

We investigate this question by introducing a complexity-theoretic framework, which allows us to shed some light on the role of randomness in the LOCAL model. In particular, we prove completeness results which, roughly speaking, show that some rather rudimentary-looking problems are “complete” for essentially all the classic local distributed problems. In other words, if any of these complete problems can be solved deterministically in $\poly\log n$ rounds in the LOCAL model, we can deterministically solve essentially all the classic LOCAL-problems (including MIS and $(\Delta+1)$-coloring) in $\poly\log n$ rounds.

Perhaps the most surprising complete problem is the following: Color the nodes of the graph red or blue such that each node of a sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized algorithm, simply color each node randomly. This completeness result can be viewed as showing that the only obstacle to getting efficient deterministic algorithms in the LOCAL model is an efficient algorithm to round fractional values into integer values, while approximately preserving some linear constraints.

This talk is based on a joint work with Fabian Kuhn and Yannic Maus.

A version of the paper can be found here: https://arxiv.org/abs/1611.02663

TCS+ talk: Wednesday, May 10 — Avishay Tal, IAS

The next TCS+ talk will take place next Wednesday, May 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Avishay Tal (IAS) will will speak about “Computing Requires Larger Formulas than Approximating” (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.

A de-Morgan formula over Boolean variables x_1, …, x_n is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that some explicit function (in P or NP) requires large formulas is a central open question in computational complexity.

In this work, we introduce a size-amplification hardness reduction for de-Morgan formulas. We show that average-case hardness implies worst-case hardness for a larger size. More precisely, if a function f cannot be computed correctly on more than 1/2 + eps of the inputs by any formula of size s, then computing f correctly on all inputs requires size ~s*log(1/eps). The tradeoff is essentially tight. Quite surprisingly, the proof relies on a result from quantum query complexity by Reichardt [SODA, 2011].

As an application, we improve the best known formula size lower bounds for explicit functions by logarithmic factors to ~n^3/log(n). In addition, we propose candidates for explicit functions that we believe have formula size ~n^4, and prove non trivial super-quadratic formula size lower bounds for them using our reduction.

TCS+ talk: Wednesday, April 26 — Santosh Vempala, Georgia Tech

The next TCS+ talk will take place next Wednesday, April 26th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Santosh Vempala (Georgia Tech) will present joint work with Yin Tat Lee to appear in STOC’17, “Sampling Polytopes: From Euclid to Riemann”  (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 introduce the Geodesic Walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from the interior of a convex polytope in n-dimensional Euclidean space. The walk is a simulation of a stochastic differential equation defined using a convex barrier function; each step is the solution of an ordinary differential equation. It improves the time complexity of sampling polytopes and is the first walk to achieve sub-quadratic complexity. Most of the talk will be spent introducing relevant aspects of manifolds, stochastic processes, efficient solution of differential equations, and how this walk overcomes the bottlenecks of random walks in Euclidean space. No background in string theory (or Riemannian geometry) will be assumed.

Joint work with Lee Yin Tat.

TCS+ talk: Wednesday, April 12 — Kasper Green Larsen, Aarhus

The next TCS+ talk will take place next Wednesday, April 12th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Kasper Green Larsen (Aarhus) will present joint work with Weinstein and Yu, “Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds”  (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.

This talks presents the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\lg^{1.5} n)$ lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over F_2 ([Pat07]). Proving an $\omega(\lg n)$ lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Patrascu’s obituary [Tho13]. This result also implies the first $\omega(\lg n)$ lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-boolean) problems of range selection and range median.

Our technical centerpiece is a new way of “weakly” simulating dynamic
data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebychev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the “cell sampling” method of Panigrahy et al. [PTW10].

TCS+ talk: Wednesday, March 29 — Noah Stephens-Davidowitz, NYU

TCS+ is resuming! Our next talk will take place next Wednesday, March 29th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Noah Stephens-Davidowitz (NYU) will present joint work with Oded Regev on “A Reverse Minkowski Theorem”, to appear in the next STOC  (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.

A classical problem in the geometry of numbers asks us to estimate how many lattice points lie in some ball around the origin. Minkowski’s celebrated theorem gives us a tight lower bound for this number that depends only on the determinant of the lattice. (One can think of the determinant as the limit of the density of lattice points inside large balls. So, Minkowski’s theorem gives a tight lower bound on a lattice’s “local density” based on its “global density.”) We resolve a conjecture due to Dadush that gives a nearly tight converse to Minkowski’s theorem—an upper bound on the number of lattice points in a ball that depends only on the determinants of sublattices. This theorem has numerous applications, from complexity theory, to the geometry of numbers, to the behavior of Brownian motion on flat tori.

Based on joint work with Oded Regev.