TCS+

A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, April 1 — Venkat Guruswami, CMU

The next TCS+ talk will take place this coming Wednesday, April 1th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Venkat Guruswami from CMU will speak about “Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. (The link will also be posted on our website on the day of the talk, so people who did not sign up will still be able to join, until the maximum capacity of 300 seats is reached.) 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: We establish a constructive version of Shannon’s noisy coding theorem for binary codes, with information rate converging near-optimally fast to channel capacity as a function of code length. Specifically, let W be an arbitrary binary-input memoryless symmetric channel with Shannon capacity I(W), and fix any \delta >0. We construct, for any sufficiently small \varepsilon >0, binary linear codes of block length O(1/\varepsilon^{2+\delta}) and rate I(W)-\varepsilon that enable reliable communication on W with quasi-linear time encoding and decoding. Shannon’s theorem implies the existence of such codes (without efficient constructions or decoding) with block length O(1/\varepsilon^2). This quadratic dependence on the gap epsilon to capacity is known to be best possible. Previously such a construction was only known for the case of the erasure channel.

Our codes are a variant of Arıkan’s polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A key technical ingredient in the analysis is a strong converse to the noisy coding theorem that shows extreme unpredictability of even a single message bit when communicating via random linear codes at rates slightly above capacity.

Joint work with Andrii Riazanov and Min Ye.

 

TCS+ talk: Wednesday, March 25 — Dana Moshkovitz, UT Austin

The next TCS+ talk will take place this coming Wednesday, March 25th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Dana Moshkovitz from UT Austin will speak about “Nearly Optimal Pseudorandomness From Hardness” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. (The link will also be posted on our website on the day of the talk, so people who did not sign up will still be able to join, until the maximum capacity of 300 seats is reached.) 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: Existing proofs that deduce BPP=P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against randomized single-valued nondeterministic (SVN) circuits, we convert any randomized algorithm over inputs of length n running in time t\geq n to a deterministic one running in time t^{2+\alpha} for an arbitrarily small constant \alpha > 0. Such a slowdown is nearly optimal, as, under complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that errs rarely into a deterministic algorithm having a similar running time (with pre-processing). The latter derandomization result holds under weaker assumptions, of exponential lower bounds against deterministic SVN circuits. Our results follow from a new, nearly optimal, explicit pseudorandom generator. The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.

 

Updated Spring schedule: increased talk frequency, and joining as individuals

We hope you are all as safe and sound as possible these days, and will be for the weeks to come.

For those of you confined at home, it may be hard to remain connected with the TCS community or stay up-to-date with the current research, as in-person seminars and conferences are cancelled. In case this may help, we have decided to increase for now the frequency of our online seminars, to try and mitigate this aspect. This won’t restore normalcy, but every little thing counts.

Here is our current, now weekly schedule: we may add more talks to it in the days to come, so keep an eye on our calendar and don’t hesitate to suggest talks and results you are curious about.

  • 03/25: Dana Moshkovitz (UT Austin) on “Nearly Optimal Pseudorandomness From Hardness”
  • 04/01: Venkat Guruswami (CMU) on “Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity”
  • 04/08: Rahul Ilango (MIT) on “NP-Hardness of Circuit Minimization for Multi-Output Functions”
  • 04/15: Ramon van Handel (Princeton) on “Rademacher type and Enflo type coincide”
  • 04/22: Huacheng Yu (Princeton) on “Nearly Optimal Static Las Vegas Succinct Dictionary”
  • 04/29: Sepideh Mahabadi (TTIC) on “Non-Adaptive Adaptive Sampling on Turnstile Streams”

We emphasize that you can (and should) join as individuals, from home: if you are interested in a talk, ask for a spot for yourself, no need to go to your institution. We have the live audience capacity for this to work, so don’t hesitate!

We will post individual announcements several days before each talk, including the abstracts and how to ask for a spot, as usual; and the talks will of course be available on YouTube and our website afterwards if you couldn’t make it to the live, interactive one. Crucially, we would like your feedback: not only talk suggestions as pointed out before, but also any idea or suggestion you may have of things we could do or implement, or of content you would like to see. You can send us feedback by emailing any of our organizers, or leaving a comment below.

Stay safe,

The TCS+ team

Note: you don’t need to sign up in advance (the link will be made public on our website the day of the talk, and you can just join then). We only encourage you to do so in order for us to get a sense of the audience size, but it’s optional: don’t feel you have to plan ahead!

TCS+ talk: Wednesday, March 11 — Thomas Steinke, IBM Research Almaden

The next TCS+ talk will take place this coming Wednesday, March 11th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Thomas Steinke from IBM Research Almaden will speak about “Reasoning About Generalization via Conditional Mutual Information” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. In view of the recent travel restrictions and coronavirus precautions, in particular, do not hesitate to reserve a seat even for a group of size one: there should be enough room for everyone, so don’t be shy!

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: We provide an information-theoretic framework for studying the generalization properties of machine learning algorithms. Our framework ties together existing approaches, including uniform convergence bounds and recent methods for adaptive data analysis. Specifically, we use Conditional Mutual Information (CMI) to quantify how well the input (i.e., the training data) can be recognized given the output (i.e., the trained model) of the learning algorithm. We show that bounds on CMI can be obtained from VC dimension, compression schemes, differential privacy, and other methods. We then show that bounded CMI implies various forms of generalization.

Based on joint work with Lydia Zakynthinou.

TCS+ talk: Wednesday, February 26 — Henry Yuen, University of Toronto

The next TCS+ talk will take place this coming Wednesday, February 26th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Henry Yuen from University of Toronto will speak about “MIP* = RE” (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: MIP* denotes the class of problems that admit interactive proofs with quantum entangled provers. It has been an outstanding question to characterize the complexity of MIP*. Most notably, there was no known computable upper bound on this class.
We show that MIP* is equal to the class RE, the set of recursively enumerable languages. In particular, this shows that MIP* contains uncomputable problems. Through a series of known connections, this also yields a negative answer to Connes’ Embedding Problem from the theory of operator algebras. In this talk, I will explain the connection between Connes’ Embedding Problem, quantum information theory, and complexity theory. I will then give an overview of our approach, which involves reducing the Halting Problem to the problem of approximating the entangled value of nonlocal games.
Joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright.

TCS+ talk: Wednesday, February 12 — Albert Atserias, Universitat Politecnica de Catalunya

The next TCS+ talk will take place this coming Wednesday, February 12th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Albert Atserias from Universitat Politecnica de Catalunya will speak about “Automating Resolution is NP-Hard” (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: We show that it is NP-hard to distinguish CNF formulas that have Resolution refutations of almost linear length from CNF formulas that do not even have weakly exponentially long ones. It follows from this that Resolution is not automatable in polynomial time unless P = NP, or in weakly exponential time unless ETH fails. The proof of this is simple enough that all its ideas can be explained in a talk. Along the way, I will try to explain the process of discovery that led us to the result. This is joint work with Moritz Müller.

 

TCS+: Spring approaches, talks resume!

The winter hiatus is nearly over, and the new season of TCS+ is about to start! Our first two talks will take place on Feb 12th and 26th, respectively. We’re pretty excited about them…

  • On February 12th, 1pm EST, Albert Atserias (Universitat Politecnica de Catalunya) will tell us all about how Automating Resolution is NP-Hard.
  • Then, on February 26th, Henry Yuen (University of Toronto) will speak about the recent proof that MIP*=RE.

Stay tuned for the official talk announcements. And this is only the beginning of the semester…

In the meantime, if you have suggestions, here is the link.