Theory of Computing Blog Aggregator

Private Set Intersection (PSI) is a problem within the broader field of secure computation. The PSI problem There are two friends Alice and Bob such that Alice has a set of items $A=(a_1,\ldots,a_n)$ and Bob has the set $B=(b_1,\ldots,b_n)$. The goal is to design a protocol by which Alice and...

at March 29, 2020 08:00 AM UTC

Game theory, a graduate course at IDC, Herzliya; Lecturer: Gil Kalai; TA: Einat Wigderson,  ZOOM mentor: Ethan.

Starting Tuesday March 31, I am giving an on-line course (in Hebrew) on Game theory at IDC, Herzliya (IDC English site; IDC Chinese site). There will be a page here on the blog devoted to this course.

In addition to the IDC moodle (course site) that allows IDC students to listen to recorded lectures, submit solutions to problem sets , etc., there will be a page here on the blog devoted to the course.

A small memory: In 1970 there was a strike in Israelis’ high schools and I took a few classes at the university. One of these classes was Game theory and it was taught by Michael Maschler. (I also took that trimester a course on art taught by Ziva Meisels.) Our department at HUJI is very strong in game theory, but once all the “professional” game theorists retired, I gave twice a game theory course which I enjoyed a lot and it was well accepted by students. In term of the number of registered students, it seems that this year’s course at IDC is quite popular and I hope it will be successful.

The first six slides of the first presentation

(Click to enlarge)

Game Theory 2020, games, decisions, competition, strategies, mechanisms, cooperation

The course deals with basic notions, central mathematical results, and important examples in non-cooperative game theory and in cooperative game theory, and with connections of game theory with computer science, economics and other areas.

What we will learn

1. Full information zero-sum games. The value of a game. Combinatorial games.

2. Zero-sum games with incomplete information. Mixed strategies, the Minmax Theorem and the value of the game.

3. Non cooperative games, the prisoner dilemma, Nash equilibrium, Nash’s theorem on the existence of equilibrium.

4. Cooperative games, the core and the Shapley value. Nash bargaining problem, voting rules and social choice.

Background material:

Game theory alive by Anna Karlin and Yuval Peres (available on-line).

In addition I may use material from several books in Hebrew by Maschler, Solan, Zamir, by Hefetz, and by Megiddo (based on lectures by Peleg). (If only I will manage to unite with my books that are not here.) We will also use a site by Ariel Rubinstein for playing games and some material from the book by Osborne and Rubinstein.

Requirement and challenges:

  • Play, play, play games, in Ariel Rubinshtein site and various other games.
  • Solve 10 short theoretical problem set.
  • Final assignment, including some programming project that can be carried out during the semester.
  • Of course, we will experience on-line study which is a huge challenge for us all.

Games and computers

  • Computer games
  • Algorithms for playing games
  • algorithmic game theory:
    • Mechanism design
    • Analyzing games in tools of computer science
    • Electronic commerce
  • Games, logic and automata: there will be a parallel course by Prof. Udi Boker

I still have some difficulty with the virtual background in ZOOM.

by Gil Kalai at March 28, 2020 09:19 PM UTC

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.


by plustcs at March 28, 2020 04:46 PM UTC

Graph Theorist and Georgia Tech Math Professor Robin Thomas passed away Thursday after his long battle with ALS. He was one of the giants of the field and a rare double winner of the Fulkerson Prize, for the six-color case of the Hadwiger Conjecture and the proof of the strong perfect graph theorem.

If you start with a graph G and either delete some vertices or merge vertices connected by an edge, you get a minor of G. The Hadwiger conjecture asks whether every graph that is not (k+1)-colorable graph has a clique of size k as a minor. Neil Robertson, Paul Seymour and Thomas proved the k=6 case in 1993 and still the k>6 cases remain open.

A graph is perfect if its maximum clique size is equal to its chromatic number. In 2002 Maria Chudnovsky, Robertson, Seymour and Thomas showed that a graph G is not perfect if and only if either G or the complement of G has an induced odd cycle of length greater than 3.

Robin Thomas was already confined to a wheelchair when I arrived at Georgia Tech in 2012. He was incredibly inspiring as he continued to teach and lead the Algorithms, Combinatorics and Optimization PhD program until quite recently. Our department did the ALS challenge for him. In 2016 he received the Class of 1934 Distinguished Professor Award, the highest honor for a professor at Georgia Tech.  He'll be terribly missed.

by Lance Fortnow ( at March 28, 2020 03:40 PM UTC

Authors: Eric Barszcz
Download: PDF
Abstract: This paper introduces a polynomial blind algorithm that determines when two square matrices, $A$ and $B$, are permutation similar. The shifted and translated matrices $(A+\beta I+\gamma J)$ and $(B+\beta I+\gamma J)$ are used to color the vertices of two square, edge weighted, rook's graphs. Then the orbits are found by repeated symbolic squaring of the vertex colored and edge weighted adjacency matrices. Multisets of the diagonal symbols from non-permutation similar matrices are distinct within a few iterations, typically four or less.

at March 28, 2020 12:00 AM UTC

Authors: Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, Manolis Zampetakis
Download: PDF
Abstract: The classes PPA-$p$ have attracted attention lately, because they are the main candidates for capturing the complexity of Necklace Splitting with $p$ thieves, for prime $p$. However, these classes are not known to have complete problems of a topological nature, which impedes any progress towards settling the complexity of the problem. On the contrary, such problems have been pivotal in obtaining completeness results for PPAD and PPA, for several important problems, such as finding a Nash equilibrium [Daskalakis et al., 2009, Chen et al., 2009b] and Necklace Splitting with 2 thieves [Filos-Ratsikas and Goldberg, 2019].

In this paper, we provide the first topological characterization of the classes PPA-$p$. First, we show that the computational problem associated with a simple generalization of Tucker's Lemma, termed $p$-polygon-Tucker, as well as the associated Borsuk-Ulam-type theorem, $p$-polygon-Borsuk-Ulam, are PPA-$p$-complete. Then, we show that the computational version of the well-known BSS Theorem [Barany et al., 1981], as well as the associated BSS-Tucker problem are PPA-$p$-complete. Finally, using a different generalization of Tucker's Lemma (termed $\mathbb{Z}_p$-star-Tucker), which we prove to be PPA-$p$-complete, we prove that $p$-thieves Necklace Splitting is in PPA-$p$. All of our containment results are obtained through a new combinatorial proof for $\mathbb{Z}_p$-versions of Tucker's lemma that is a natural generalization of the standard combinatorial proof of Tucker's lemma by Freund and Todd [1981]. We believe that this new proof technique is of independent interest.

at March 28, 2020 12:00 AM UTC

Authors: Lintao Ye, Nathaniel Woodford, Sandip Roy, Shreyas Sundaram
Download: PDF
Abstract: Given a linear dynamical system affected by stochastic noise, we consider the problem of selecting an optimal set of sensors (at design-time) to minimize the trace of the steady state a priori or a posteriori error covariance of the Kalman filter, subject to certain selection budget constraints. We show the fundamental result that there is no polynomial-time constant-factor approximation algorithm for this problem. This contrasts with other classes of sensor selection problems studied in the literature, which typically pursue constant-factor approximations by leveraging greedy algorithms and submodularity (or supermodularity) of the cost function. Here, we provide a specific example showing that greedy algorithms can perform arbitrarily poorly for the problem of design-time sensor selection for Kalman filtering. We then study the problem of attacking (i.e., removing) a set of installed sensors, under predefined attack budget constraints, to maximize the trace of the steady state a priori or a posteriori error covariance of the Kalman filter. Again, we show that there is no polynomial-time constant-factor approximation algorithm for this problem, and show specifically that greedy algorithms can perform arbitrarily poorly.

at March 28, 2020 11:20 PM UTC

Authors: Nir Goren, Dan Halperin, Sivan Toledo
Download: PDF
Abstract: We show how to efficiently solve a clustering problem that arises in a method to evaluate functions of matrices. The problem requires finding the connected components of a graph whose vertices are eigenvalues of a real or complex matrix and whose edges are pairs of eigenvalues that are at most \delta away from each other. Davies and Higham proposed solving this problem by enumerating the edges of the graph, which requires at least $\Omega(n^{2})$ work. We show that the problem can be solved by computing the Delaunay triangulation of the eigenvalues, removing from it long edges, and computing the connected components of the remaining edges in the triangulation. This leads to an $O(n\log n)$ algorithm. We have implemented both algorithms using CGAL, a mature and sophisticated computational-geometry software library, and we demonstrate that the new algorithm is much faster in practice than the naive algorithm. We also present a tight analysis of the naive algorithm, showing that it performs $\Theta(n^{2})$ work, and correct a misrepresentation in the original statement of the problem. To the best of our knowledge, this is the first application of computational geometry to solve a real-world problem in numerical linear algebra.

at March 28, 2020 11:26 PM UTC

Authors: Boris Aronov, Jean Cardinal
Download: PDF
Abstract: We prove that some exact geometric pattern matching problems reduce in linear time to $k$-SUM when the pattern has a fixed size $k$. This holds in the real RAM model for searching for a similar copy of a set of $k\geq 3$ points within a set of $n$ points in the plane, and for searching for an affine image of a set of $k\geq d+2$ points within a set of $n$ points in $d$-space.

As corollaries, we obtain improved real RAM algorithms and decision trees for the two problems. In particular, they can be solved by algebraic decision trees of near-linear height.

at March 28, 2020 12:00 AM UTC

Authors: Giulio Ermanno Pibiri, Rossano Venturini
Download: PDF
Abstract: The representation of a dynamic ordered set of $n$ integer keys drawn from a universe of size $m$ is a fundamental data structuring problem. Many solutions to this problem achieve optimal time but take polynomial space, therefore preserving time optimality in the \emph{compressed} space regime is the problem we address in this work. For a polynomial universe $m = n^{\Theta(1)}$, we give a solution that takes $\textsf{EF}(n,m) + o(n)$ bits, where $\textsf{EF}(n,m) \leq n\lceil \log_2(m/n)\rceil + 2n$ is the cost in bits of the \emph{Elias-Fano} representation of the set, and supports random access to the $i$-th smallest element in $O(\log n/ \log\log n)$ time, updates and predecessor search in $O(\log\log n)$ time. These time bounds are optimal.

at March 28, 2020 12:00 AM UTC

Authors: Yasuaki Kobayashi
Download: PDF
Abstract: Node Kayles is a well-known two-player impartial game on graphs: Given an undirected graph, each player alternately chooses a vertex not adjacent to previously chosen vertices, and a player who cannot choose a new vertex loses the game. The problem of deciding if the first player has a winning strategy in this game is known to be PSPACE-complete. There are a few studies on algorithmic aspects of this problem. In this paper, we consider the problem from the viewpoint of fixed-parameter tractability. We show that the problem is fixed-parameter tractable parameterized by the size of a minimum vertex cover or the modular-width of a given graph. Moreover, we give a polynomial kernelization with respect to neighborhood diversity.

at March 28, 2020 12:00 AM UTC

Authors: Dmitriy Zhuk
Download: PDF
Abstract: Surjective Constraint Satisfaction Problem (SCSP) is the problem of deciding whether there exists a surjective assignment to a set of variables subject to some specified constraints. In this paper we show that one of the most popular variants of the SCSP, called No-Rainbow Problem, is NP-Hard.

at March 28, 2020 11:22 PM UTC

Authors: Timothy M. Chan, Qizheng He, Yakov Nekrich
Download: PDF
Abstract: We present a number of new results about range searching for colored (or "categorical") data:

1. For a set of $n$ colored points in three dimensions, we describe randomized data structures with $O(n\mathop{\rm polylog}n)$ space that can report the distinct colors in any query orthogonal range (axis-aligned box) in $O(k\mathop{\rm polyloglog} n)$ expected time, where $k$ is the number of distinct colors in the range, assuming that coordinates are in $\{1,\ldots,n\}$. Previous data structures require $O(\frac{\log n}{\log\log n} + k)$ query time. Our result also implies improvements in higher constant dimensions.

2. Our data structures can be adapted to halfspace ranges in three dimensions (or circular ranges in two dimensions), achieving $O(k\log n)$ expected query time. Previous data structures require $O(k\log^2n)$ query time.

3. For a set of $n$ colored points in two dimensions, we describe a data structure with $O(n\mathop{\rm polylog}n)$ space that can answer colored "type-2" range counting queries: report the number of occurrences of every distinct color in a query orthogonal range. The query time is $O(\frac{\log n}{\log\log n} + k\log\log n)$, where $k$ is the number of distinct colors in the range. Naively performing $k$ uncolored range counting queries would require $O(k\frac{\log n}{\log\log n})$ time.

Our data structures are designed using a variety of techniques, including colored variants of randomized incremental construction (which may be of independent interest), colored variants of shallow cuttings, and bit-packing tricks.

at March 28, 2020 12:00 AM UTC

Authors: Tomoyuki Morimae
Download: PDF
Abstract: The posthoc verification protocol [J. F. Fitzsimons, M. Hajdu{\v s}ek, and T. Morimae, Physical Review Letters {\bf120}, 040501 (2018)] enables an information-theoretically-sound non-interactive verification of quantum computing, but the message from the prover to the verifier is quantum and the verifier has to do single-qubit measurements. The Mahadev protocol removes these quantum parts, but the soundness becomes the computational one. In this paper, we construct an information-theoretically-sound non-interactive classical verification protocol for quantum computing with a trusted center. The trusted center sends random BB84 states to the prover, and the classical descriptions of these BB84 states to the verifier. The messages from the center to the prover and the verifier are independent of the instance. By slightly modifying our protocol, we also construct a non-interactive statistical zero-knowledge proof system for QMA with the trusted center.

at March 28, 2020 11:22 PM UTC

Our community has some outstanding long-running virtual seminars, and there are many traditional seminars now moving to a virtual format.  Northwestern Ph.D. students Modibo Camara and Yiding Feng have a collection of them in a Google Calendar at Virtual CS+Econ Seminars.  Don’t miss any of the action!

The topics include but not limited to theoretical computer science, economic theory, theoretical machine learning, and econometrics.  The calendar currently tracks talks in Caltech Econ Theory, Chamberlain Seminar in Econometrics, IDEAL, MD4SG, and TCS+. Send other relevant talk series or one-off events to Modibo and Yiding at

by Jason Hartline at March 26, 2020 10:24 PM UTC

The approximate graph colouring problem concerns colouring a $k$-colourable graph with $c$ colours, where $c\geq k$. This problem naturally generalises to promise graph homomorphism and further to promise constraint satisfaction problems. Complexity analysis of all these problems is notoriously difficult. In this paper, we introduce two new techniques to analyse the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new NP-hardness results for a significant class of approximate graph colouring and promise graph homomorphism problems.

at March 26, 2020 02:25 PM UTC

The new coronavirus upended much of society, including our little corner of it. I believe at this point almost all theorists are teaching and doing research at home, and I thought it would be good to share some of the tools we use for doing so. Below I will describe my setup, but I hope other people share theirs too.

Teaching and virtual whiteboards

I am teaching using Zoom and using an iPad pro with a pencil to simulate a whiteboard. I use a laptop to connect to Zoom and for the camera, laptop, and chat window, and then join the iPad.There are several ways to connect an iPad to a Zoom session:

  1. Join the session from the iPad separately using the iPad Zoom app. (To do so you need to logout of your other account.)
  2. Within desktop Zoom you can choose “share screen” and then one of the option is to join an iPad connected to the same wireless network as the laptop/desktop and use “screen mirroring”.
  3. You can use a wired connection, which is either by just connecting through USB (in a Mac) or a complex combination of combining an adapter to take an HDMI signal out of an iPad with an HDMI capture card to stream this signal to the computer.

I use option 2. The main reason I prefer it is because the application I use for a whiteboard – GoodNotes – has a presentation mode that behaves differently when you are connected to an external display or use AirPlay (which is what option 2 does). In this presentation mode the students don’t see your interface, and so you can Zoom, go to the page selector and more without it disturbing what they see. GoodNotes also has a great “laser pointer”. I set the pages at a landscape orientation, and pre-write a good chunk of what I plan to present before the lecture. I also use the ability to “duplicate pages” to achieve the PowerPoint like effect of gradual reveal.

It is not perfect – I’ve discovered that the screen share sometimes stops refreshing and I need to leave GoodNotes and return to it for it to go back.

Monitoring the chat window and raised hands in Zoom is non-trivial. It helps a lot that I have a teaching assistant that participates in lecture and notices if I missed something.

Some people say that a “matte screen protector” such as PaperLike makes the iPad more comfortable to write on – haven’t yet tried it.

I have a good Webcam (Logitech Brio) but at the moment I’m not using it since it seems too taxing on my laptop and so I went back to the native webcam. I have a very nice wireless headset/mic combo (Jabra Evolve 75) that I am constantly using and have been very happy with. I particularly like the feature of being able to unmute and mute yourself by raising and lowering the mike.


For research Slack continues to extremely useful. For working jointly on a paper Overleaf is of course great, but for maintaining a shared document it sometimes useful to use simpler platform that are not full fledged LaTeX. Some options include:

Google JamBoard is an interactive whiteboard, also with an iPad app. I haven’t tried it yet but it seems promising.

Keeping children busy

For many people I imagine childcare is one of the most challenging aspects. At the moment at least the Cambridge Public Schools are not keeping my kids too busy. While probably most of their time is spent in non educational pursuits, we try to also encourage (i.e., bribe/extort/threaten/beg) them to do some learning. If your kids are interested in math, I highly recommend the courses offered by the Art of Problem Solving (they also have a theory connection: one of their books was co-authored by theorist Ravi Boppana). For younger kids you can also try their Beast Academy.

The AOPS program is not free but over the years my kids (especially my 13 year old daughter Alma) have also spent a lot of time on the free and amazing Khan Academy. In fact, last year she was inspired enough by Khan’s JavaScript course to write the following poem which (for obvious reasons) moved me very much:

Tending / Alma Barak

My mind is a desert
of boredom
of blankness
of leaning-back-in-your-chairness
and of simply-staring-at-the-ceilingness
I kick at a crumpled
deserted baby-blonde post-it
with my spotted socked feet
waiting for Aba to come.

We dive when he comes
into the seas of Khan
free-styling our way
into the lakes of Java
we pass codes we already
while loops
for loops
reminding me of what I’d learned

We frog-kick to an
lagoon of code I don’t know
sometimes I get swept away by currents
of confusion
but my aba, my dad
grabs my hand
and shows me the way through
teaching me
tending to me
washing away the sands of boredom with the sea of Khan.

by Boaz Barak at March 26, 2020 12:52 PM UTC

We consider the univariate polynomial $f_d:=(x+1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$. We show a stunning connection of the conjecture to the two main problems in algebraic complexity: Polynomial Identity Testing (PIT) and VP vs VNP. Our conjecture on $f_d$ implies blackbox-PIT in P. Assuming the Generalized Riemann Hypothesis (GRH), it also implies VP $\neq$ VNP. No such connection to PIT, from lower bounds on constant-powers representation of polynomials was known before. We establish that studying the expression of $(x+1)^d$, as the sum of $25^{th}$-powers of univariates, suffices to solve the two major open questions. In support, we show that our conjecture holds over the integer ring of any number field. We also establish a connection with the well-studied notion of matrix rigidity.

at March 25, 2020 09:21 PM UTC

Shcachar Lovett has put together a new website aggregating information about virtual talks in CS theory:

 It has a Google calendar that people can add to their own, and a form to submit a new talk that automatically gets added to the Google calendar. 

This can be a fantastic resource these days that almost no one can travel – please publicize this and also submit to it talks that you are organizing.

by Boaz Barak at March 25, 2020 05:00 PM UTC

The Department of Computer Science at TU Dortmund University ( is seeking to fill the position of a Full Professor Position (W3) in “Efficient Algorithms and Complexity Theory” commencing as soon as possible.


by shacharlovett at March 24, 2020 10:41 AM UTC

Lance had a great post on what to do while you are stuck at home, which is of course relevant to whats happening now. Lance's post is here.

I will add to it, and then have other comments.

1) In our current electronic society we can do a lot from home. Don't think of it as being `stuck at home'

2) Lance points out that you should read a paper, read a textbook, etc. I of course agree and add some advice. Be Goldlocks!

This paper is too hard (e.g., a text on quantum gravity)

This paper is too easy (e.g., a discrete  math textbook for a freshman course)

This paper is just right (e.g., working out the large canonical Ramsey theorem)

3) If you catch up on your TV viewing on your DVR then beware: you will see commercials for Bloomberg.

4) DO NOT binge watch TV.  You will hate yourself in the morning.

5) Simons Inst Theory talks:

TCS+ talks


The Gathering for Gardner records all of their talks and puts the on you-tube
so goto youtube and search for Gathering for Gardners. These are Goldilocks talks since they
are easy but on stuff you prob don't know.

6) Keep fit. I used to go on treadmill for 45 minutes a day, now I am doing an hour.

7) Go for walks with a person who already shares your house, but avoid other people.

8) Book reviews, surveys, orig articles, that you were putting off writing- now write them.
but see next item.

10) Catch up on your blog reading. My favorite was Scott Aaronson's blog post about Davos:here. I also read every single comment. I hated myself in the morning. So that part may have been a mistake.


1) Do you really have more free time? No commuting, no teaching, but you still have the rest of your job, and perhaps it is harder if some things are easier at work. And calling relatives and friends to make sure they are okay, and just to talk, is a great thing to do, but its time consuming.

2) I'm beginning to lose track of what day-of-the-week it is since I don't have school to keep me on track, and I only watch TV shows on DVR so I watching a show on a day does not mean I know what day it is.

3) Avoid being price-gouged. The first few days that I tried to buy TP for my mom on amazon (I do this in normal times--- I order lots for my mom on amazon--- she is tech shy. She is also over 90.) her usual brand was out of stock, and the other brands were either higher quality so higher prices or just
absurdly priced. She wisely said to wait a week. She was right- it was easy to get at the usual price.

4) More generally, it seems like the shortages are people-created. For example, if in a store you see they are low on X, then you buy LOTS of X, and everyone does that, so then their really is a shortage of X. But I think thats calmed down some.

5) It important to have a `we will recover from this, life will go on' attitude (while following the things ALL experts say- wash your hands a lot, drink lots of water, get lots of sleep, which is prob
good advice anyway) and hence I will try to, for the next few weeks, blog on NORMAL things----Hilberts's 10th problem, Large Ramsey, etc.

ADDED LATER- there is a very nice contrarian view in the comment by Steve, the first comment. You should read that!

by GASARCH ( at March 24, 2020 04:01 AM UTC

The Protezione Civile, the Italian equivalent of FEMA, holds a daily press conference to announce coronavirus data from the previous 24 hours. Today they had relatively good news, of which we hope to hear more soon. The Protezione Civile puts a lot of data online every day, on github, which allows any interested party to monitor the situation and will allow people in other countries to see the effect of our various restrictive measures over time.

The graph below, which is courtesy of Carlo Lucibello, shows the number of deaths in Italy on a logarithmic scale, compared with data from China from 36 days before.
(Image credit: Carlo Lucibello)

At the start, Italian deaths rose like in China, at the same exponential rate. About twenty days after the lockdown of Wuhan, the Chinese data started deviating from the exponential rate and leveled off. In Italy, about ten days ago, there was a slowdown, which followed the institution of the “yellow zone” by about 15 days. The “yellow zone” measures closed schools, universities, museums, cinemas, and clubs, and restricted hours of bars and coffee shops, in Lombardy. Apparently, although these measures made a difference, they still allowed the spread of the virus to continue at an exponential rate.

On March 8, Lombardy was put on a stricter lockdown, with travel restrictions, and on March 10 the lockdown was extended to the rest of the country. So we may hope to see a stronger slowdown and maybe a leveling-off two or three weeks after these measures, that is, any day now. It may seem premature to ask this question, but what happens next?

Today the Italian government announced additional measures to facilitate “social distancing,” halting all “non-essential” manufacturing and other work activities, forbidding people from leaving the house to walk or jog (even alone), and further restricting the cases in which it is allowed to travel between different cities.

These measures, which apply nationwide, are meant to be in place for two weeks. They will be economically devastating (even more so than the already devastating nationwide lockdown of March 10), and they will be difficult to keep in place for longer than the expected two weeks.

When a nationwide “lockdown” was first instituted, the prime minister announced it by saying “let’s be distant today in order to more warmly hug each other tomorrow”. In general, the spirit of these measures has been to suffer for a short time and then return to normal.

This feels like the national mood in general, and the government took today’s further restrictive measures somewhat reluctantly, because there was strong popular support for them.

Here I am worried that we are approaching this crisis the way many people attempt to lose weight: by going on a starvation diet, then losing some weight, then celebrating and finally gaining back more weight than they lost.

The point being that I worry about what will happen once the worst is over and these restrictive measures will be lifted. Until there is a vaccine or a cure, we will not be able to really go back to normal, and we will have to make some sustainable “lifestyle changes” to “maintain” what we got, just like people who maintain weight loss for a long time do so by making sustainable changes for the long term.

Concretely, we will need a very efficient system to monitor new cases and trace contacts, perhaps similar to Taiwan’s, and to follow the kind of stricter hygiene precautions in public places that have been common in East Asia since SARS. Let’s hope that we will have to worry about such problems soon.

by luca at March 22, 2020 10:08 PM UTC

The UCI Ecological Preserve is a 60-acre patch of coastal sage scrub, adjoining the housing complex in which I live.

Like most of the rest of the world, I’m stuck at home for an indefinite duration, but the level of lockdown that we’re under allows us to go for walks outside, and like many of my neighbors (keeping a safe distance from each other) I took advantage of the opportunity to do so yesterday in the preserve. It was a gorgeous day, with very clear air from the recent rains: so clear that I could see individual buildings in downtown Los Angeles, 40 miles away.

I brought my camera along, but chose to focus on the nearby brush rather than the more distant views. Here’s one of my shots:

UCI Ecological Preserve

The rest are in my online gallery.

(Discuss on Mastodon)

by David Eppstein at March 22, 2020 03:28 PM UTC

Let me briefly report on a remarkable new paper by Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra, Revisiting Bourgain-Kalai and Fourier Entropies. The paper describes substantial progress towards the Entropy-Influence conjecture, posed by Ehud Friedgut and me in 1996. (See this blog post from 2007.)

Abstract: The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is o(logn), however, both results become useless when the total influence of the function is ω(logn). The only case in which this logarithmic barrier has been broken for an interesting class of function was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of S_n.

In this paper, we revisit the key ideas of the Bourgain-Kalai paper. We prove a new general inequality that upper bounds the correlation between a Boolean function f and a real-valued, low degree function g in terms of their norms, Fourier coefficients and total influences.

Some corollaries of this inequality are:

  1. The Bourgain-Kalai result.
  2. A slightly weaker version of the Fourier-Entropy Conjecture. More precisely, we prove that the Fourier entropy of the low-degree part of f is at most O(I[f]log^2 I[f]), where I[f] is the total influence of f. In particular, we conclude that the Fourier spectrum of a Boolean function is concentrated on at most 2O(I[f]log^2 I[f]) Fourier coefficients.
  3. Using well-known learning algorithms of sparse functions, the previous point implies that the class of functions with sub-logarithmic total influence (i.e. at most O(\log n/(\log \log n)2)) is learnable in polynomial time, using membership queries.

Our theorem on influence under symmetry. From my videotaped lecture on Jean Bourgain. See this post about Jean Bourgain.

A few remarks:

A) Given a Boolean function f:\{-1,1\}^n\to \{-1,1\} let f=\sum_{S \subset \{1,2,\dots ,n\}}\hat f(S)W_S be its Fourier-Walsh expansion. (Here W_S(x_1,x_2,\dots ,x_n)=\prod_{i\in S}x_i.) The total influence I(f) of f is described by

I(f)=\sum {S \subset \{1,2,\dots ,n\}}\hat f^2(S)|S|.

The spectral entropy E(f) of f is defined by

E(f)=\sum_{S \subset \{1,2,\dots ,n\}}\hat f^2(S) \log (\hat f^2(S)).

The entropy-influence conjecture (here called the Fourier-entropy conjecture) asserts that for some universal constant C

I(f) \ge C E(f).

B) One interesting feature of the conjecture is that the RHS is invariant under arbitrary linear transformations of \{-1,1\}^n (regarded as an n-dimensional vector space) while the LHS is invariant only to permutations of the variables.

C) My paper with Jean Bourgain, Influences of variables and threshold intervals under group symmetries, describes lower bounds on total influences for Boolean function invariant under certain groups of permutations (of the variables). Those results are stronger (but more restrictive) than what the Entropy/influence conjecture directly implies. (This was overlooked for a while.) The new paper gives (much hoped for, see below) simpler proofs and stronger results compared to those in my paper with Jean Bourgain.

D) Ryan O’Donnel wrote about Bourgain and some of his contributions to the analysis of Boolean functions:

“I spent close to 5 years understanding one 6-page paper of his (“On the distribution of the Fourier spectrum of Boolean functions”), and also close to 10 years understanding a 10-page paper of his (the k-SAT sharp threshold ‘appendix’). If anyone’s up for a challenge, I’m pretty sure no one on earth fully understands the second half of his paper “Influences of variables and threshold intervals under group symmetries” with Kalai (including Gil 🙂 )”

It looks that by now we have pretty good understanding and even some far-reaching progress regarding all three papers that Ryan mentioned. (It is unclear if we can hope now for an exponential spread of understanding for Bourgain’s proofs.)


by Gil Kalai at March 22, 2020 10:43 AM UTC

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed. We show that in this setting, it is sub-optimal to use standard error correction. We consider a model where there is a set of “valid messages” which the sender may send that may not be efficiently compressible, but where it is possible for the receiver to recognize valid messages. In this model, we construct a (probabilistic) encoding procedure that achieves better tradeoffs between data rates and error-resilience (compared to just applying a standard error correcting code). Additionally, our techniques yield improved efficiently decodable (probabilistic) codes for fully compressed messages (the standard setting where the set of valid messages is all binary strings) in the high-rate regime.

at March 22, 2020 08:59 AM UTC

Part 1 of a two-part series

Daniel Winton is a graduate student in mathematics at Buffalo. He did an independent study with me last semester on descriptive complexity.

Today we begin a two-part series written by Daniel on a foundational result in this area involving first-order logic and star-free languages.

Dick and I have discussed how GLL might act during the terrible coronavirus developments. We could collect quantitative and theoretical insights to help understand what is happening and possibly contribute to background for attempts to deal with it. Our March 12 post was this kind, and was on the wavelength of an actual advance in group testing announced in Israel two days ago, as noted in a comment. We could try to be even more active than that. We could focus on entertainment and diversion. Our annual St. Patrick’s Day post mentioned the ongoing Candidates Tournament in chess, with links to follow it live 7am–noon EDT. Game analysis may be found here and elsewhere.

Here we’re doing what we most often do: present a hopefully sprightly angle on a technical subject. We offer this in solidarity with the many professors and teachers who are beginning to teach online to many students. The subject of regular languages is the start of many theory courses and sometimes taught in high schools. Accordingly, Dick and I decided to prefix a section introducing regular languages as a teaching topic and motivating the use of logic, before entering the main body written by Daniel.

Regular Languages and Logic

Regular languages are building blocks used throughout computer science. They can be defined in many ways. Two major types of descriptions are:

  1. Regular expressions. For example, the regular expression

    \displaystyle  b^{*}(a b^{*} a b^{*})^{*}

    describes the set of strings over the alphabet {\{a,b\}} that have an even number of {a}‘s.

  2. Finite automata, for example:

The regular languages defined by (1) and (2) are the same. All regular expressions have corresponding finite automata. This equivalence makes a powerful statement about the concept of regular languages. The more and more diverse definitions we have, the better we understand a concept. This leads us to consider other possible definitions.

A natural kind of definition involves logic. Studying complexity classes through logic and model theory has proven fruitful, creating descriptive complexity as an area. Good news: there are logic definitions equivalent to the regular languages. Bad news: they require going up to second-order logic. We would like to stay with first-order logic. So we ask:

What kind of languages can we define using only first-order logic (FOL) and simple predicates like “the {i}th bit of {x} is {a}” and “place {i} comes before place {j}“?

The answer is the star-free languages, which form a subclass {\mathsf{SF}} of the regular languages. They were made famous in the book Counter-Free Automata by Robert McNaughton and Seymour Papert, where the equivalence to FOL was proved. A portentous fact is that these automata cannot solve simple tasks involving modular counting. Nor can perceptrons—the title subject of a book at the same time by Papert with Marvin Minsky, which we discussed in relation to both AI and circuit complexity. This post will introduce {\mathsf{SF}} and FOL, prove the easier direction of the characterization, and give two lemmas for next time. The second post will present a new way to visualize the other direction. The rest of this post is by Daniel Winton.

No Stars Upon Thars

A regular language over an alphabet {\Sigma} is one with an expression that can be obtained by applying the union, concatenation, and Kleene star operations a finite number of times on the empty set and singleton subsets of {\Sigma}. Star-free languages are defined similarly but give up the use of the Kleene star {{}^*} operation, while adding complementation ({\sim}) as a basic operation. The star-free languages are a subset of the regular languages, because regular languages are closed under complementation.

Complementation often helps find star-free expressions that we ordinarily write using stars. For instance, if the alphabet {\Sigma} is {\{a,b\}}, then {(\sim \emptyset)} gives {(a + b)^*}. The following lemma gives a family of regular expressions that use Kleene star but are really star-free.

Lemma 1 The language given by taking the Kleene star operation on a union of singleton elements in an alphabet {\Sigma} is star-free.

Proof. For {\Sigma=\{a_1, ..., a_n, b_1, ..., b_m\}} we have that {(b_1+ ... + b_m)^*} can be given by

\displaystyle  \sim((\sim\emptyset) (a_1+ ... + a_n) (\sim\emptyset)). \quad


For example, the language {b^*ab^*ab^*} is star-free because {b^*} is by this lemma. This idea extends also to forbidden substrings—e.g., the set of strings with no {aa} is {\;\sim((\sim\emptyset)aa(\sim\emptyset))}.

The language {(ab + ba + bb)^*} is not the same, however, and it is not star-free. Intuitively this is because it involves modular counting: an {aa} in an odd position is OK but not even. The parity language {b^*(ab^*ab^*)^*} from the introduction is another example. So {\mathsf{SF}} is a proper subset of the regular languages. What kind of subset? This is where having a third description via logic is really useful.

The First Order of Business

In addition to the familiar Boolean operations {\wedge,\vee,\neg,\rightarrow,\leftrightarrow} and truth values, first-order logic provides variables that range over elements of a structure and quantifiers on those variables. Since we will be concerned with Boolean strings {x}, the variables will range over places in the string {0,\dots,n-1}, where {n = |x|}. A logic also specifies a set of predicates that relate variables and interact with the structure. For strings we have:

  • {X_c(i)}, meaning that the symbol indexed {i} in {x} is the character {c}. The logic gives one such predicate for each {c \in \Sigma}.

  • {i < j}, with the obvious meaning for natural numbers {i} and {j}.

We can take the {X_c} for granted since we are talking about strings, but we need to say that predicates like {i + j = k} and {i\cdot j = k} are excluded, so we call this {\mathsf{FO}[<]}. We could define equality by {i = j \equiv \lnot(i < j \lor j < i)} but we regard equality as inherent.

We can use {<} to define the successor relation {S(i,j)}, which denotes that position {j} comes immediately after position {i}:

\displaystyle  S(i,j) \equiv i<j \land \forall k (i<k \rightarrow j\leq k).

Note the use of quantifiers. We can use quantifiers to say things about the string {x} too. For instance, the language {L} of strings having no {aa} substrings is defined by the logical sentence

\displaystyle  \sigma_L = (\forall i,j):S(i,j) \rightarrow \neg (X_a(i) \land X_a(j)).

It is implicit here that {i} and {j} are always in-bounds. If {n} were a legal constant with {X_c(n)} always false then a string like {bbba} (which belongs to {L}) would falsify {\sigma_L} with {i = n-1} and {j = n}.

How big is {\mathsf{FO}[<]}? We'll see it is no more and no less than {\mathsf{SF}}.

From SF to FO

To prove that any language {L} in {\mathsf{SF}} has a definition in {\mathsf{FO}}, we will not only give a sentence {\sigma_L} but also a formula {\phi_L(i,j)}. We will define this formula to indicate that for a given string {x}, the portion of the string between indices {i} and {j-1} is in {L}. Then for the correct choices of {i} and {j}, {\phi_L(i,j)} gives {L}. We define {\phi} to test middle portions of strings, because it handles lengths better for the induction in the concatenation case.

Theorem 2

Every language in {\mathsf{SF}} is definable in {\mathsf{FO}[<]}.

The proof is a nice example where “building up” to prove something more general—involving two extra variables—makes induction go smoothly.

Proof: Let {L} be a star-free regular language and {L'=\{\langle x, i ,j \rangle:} the portion of the string {x} between indices {i} (inclusive) and {j} (exclusive) is contained in {L\}}. Let {\phi_L(i,j)\in \sf{FO}[<]} be the formula denoting that for a given string {x, x[i,j)\in L}, that is, {\phi_L(i,j)} is the representation of {L'} in {\mathsf{FO}[<]}. We will show that such a {\phi_L(i,j)} exists via induction on {L}. This is sufficient, as for a given symbol {n} that always represents the length of a string {x}, {\phi_L(0,n)} is the formula in {\mathsf{FO}[<]} representing the language {L}.

First, we must show that {\phi_L} is in {\mathsf{FO}[<]} for {L} one of the basis languages, {\emptyset, \epsilon}, and {c}, for some {c} in {\Sigma}. We have that:

\displaystyle  \begin{array}{rcl}  \phi_\emptyset(i,j) &=& \texttt{false};\\ \phi_\epsilon(i,j) &=& i=j;\\ \phi_c(i,j) &=& (X_c(i)\land S(i,j)). \end{array}

Now, we must show that given star-free languages {L_1} and {L_2} with FO{[<]} translations {\psi_1(i,j)} and {\psi_2(i,j)} respectively, we have {\phi_{L_1\cup L_2}(i,j)}, {\phi_{L_1\cdot L_2}(i,j)}, and {\phi_{\sim L_1}(i,j)} are in {\sf{FO}[<]}. Then:

\displaystyle  \begin{array}{rcl}  \phi_{L_1\cup L_2}(i,j)&=&\psi_1(i,j) \lor \psi_2(i,j);\\ \\ \phi_{L_1\cdot L_2}(i,j)&=&\exists k(i\leq k \land k \leq j) (\psi_1(i,k) \land \psi_2(k,j));\\ \\ \phi_{\sim L_1}(i,j)&=&\lnot \psi_{1}(i,j). \end{array}

Since star-free languages can be obtained by applying the union, concatenation, and complementation operations a finite number of times on {\emptyset} and singleton subsets of {\Sigma}, this completes the proof of {\mathsf{SF} \subseteq \mathsf{FO}[<]}. \Box

Two Lemmas For Next Time

Prefatory to showing (in the next post) that {\mathsf{FO}[<]} is contained in {\mathsf{SF}}, we prove properties about substrings on the ends of star-free languages, rather than in the middle as with the trick in the proof of Theorem 2.

Let {L} be a language over an alphabet {\Sigma} and {w} be a word in {\Sigma^n} for some {n\in \mathbb{N}}. Define {L/w}, the right quotient of {L} by {w}, by {L/w =\{v: vw \in L\}} and {L\backslash w}, the left quotient of {L} by {w}, by {L\backslash w=\{v:wv \in L\}}. First we handle right quotients:

Lemma 3 If {L} is star-free, then {L/w} is star-free.

Proof: For any word {w} over {\Sigma} we define a function {f_w(\alpha)} by {f_w(\alpha)=\alpha'} where {L(\alpha')=L(\alpha)/w}. If {w = \epsilon}, then {f_w(\alpha)=\alpha}, and so the statement of the lemma trivially holds. So let {w = vc} for some string {v} and character {c}. Note that {L/(vc) = (L/c)/v}. Thus {f_{vc}(\alpha) = f_v(f_c(\alpha))} for all {\alpha}. Hence it suffices to define {f_c(\alpha)} for any single character {c} by recursion on {\alpha}. We have:

\displaystyle  \begin{array}{rcl}  f_c(\emptyset)&=&\emptyset;\\ f_c(\epsilon)&=&\emptyset;\\ f_c(c)&=&\epsilon;\\ f_c(a)&=&\emptyset, \end{array}

and recursively:

\displaystyle  \begin{array}{rcl}  f_c(\alpha \cup\beta)&=&f_c(\alpha) \cup f_c(\beta);\\\\ f_c(\alpha\cdot\beta)&=&\begin{cases} \alpha\cdot f_c(\beta) & \epsilon\not\in L(\beta), \\ \alpha\cdot f_c(\beta) \cup f_c(\alpha) & otherwise\text{;} \end{cases}\\\\ f_c(\sim\alpha)&=&\sim f_c(\alpha). \end{array}

In general, if {w = c_1 c_2 \cdots c_{n-1} c_n}, then

\displaystyle L/w = f_{c_1}(f_{c_2}(\dots f_{c_{n-1}}(f_{c_n}(\alpha))\dots)).


Lemma 4 If {L} is star-free, then {L\backslash w} is star-free.

The proof of Lemma 4 is similar to the proof of Lemma 3. The main differences lie in the concatenation subcase for the {w=c} case and the order of quotienting when using this operation repeatedly.

Proof: For any word {w} over {\Sigma} we define a function {f_w(\alpha)} by {f_w(\alpha)=\alpha'} where {L(\alpha')=L(\alpha)\backslash w}. If {w = \epsilon}, then {f_w(\alpha)=\alpha}, and so the statement of the lemma trivially holds. So let {w = vc} for some string {v} and character {c}. Note that {L\backslash(vc) = (L\backslash v)\backslash c}. Thus {f_{vc}(\alpha) = f_c(f_v(\alpha))} for all {\alpha}. Hence it suffices to define {f_c(\alpha)} for any single character {c} by recursion on {\alpha}. We have:

\displaystyle  \begin{array}{rcl}  f_c(\emptyset)&=&\emptyset;\\ f_c(\epsilon)&=&\emptyset;\\ f_c(c)&=&\epsilon;\\ f_c(a)&=&\emptyset.\\ \end{array}

and recursively:

\displaystyle  \begin{array}{rcl}  f_c(\alpha\cup\beta)&=&f_c(\alpha)\cup f_c(\beta);\\\\ f_c(\alpha\cdot\beta)&=&\begin{cases} f_c(\alpha)\cdot\beta & \epsilon\not\in L(\alpha), \\ f_c(\alpha)\cdot\beta \cup f_c\beta) & otherwise\text{;} \end{cases}\\\\ f_c(\sim \alpha)&=&\sim f_c(\alpha). \end{array}

In general, if {w = c_1 c_2 \cdots c_{n-1} c_n}, then

\displaystyle L\backslash w = f_{c_n}(f_{c_{n-1}}(\dots f_{c_{2}}(f_{c_1}(\alpha))\dots)).


Open Problems

There are richer systems such as {\mathsf{FO}(+)} and {\mathsf{FO}(+,\cdot)}. Note that {\mathsf{FO}(+)} allows defining the {<} relation via {i < j \equiv (\exists k) \lnot(k= 0) \land i + k = j}. We can define non-regular languages such as {{a^n b^n}} in {\mathsf{FO}(+)}. The class {\mathsf{FO}(+,\times)} famously equals uniform {\mathsf{AC^0}}, see chapter 5 of Neil Immerman's book Descriptive Complexity. Thus we hope our new style for proving {\mathsf{FO}[<] \subseteq \mathsf{SF}} (to come in the next part) will build a nice foundation for visualizing these higher results.

by KWRegan at March 21, 2020 08:54 PM UTC

We show that for every integer $k \geq 2$, the Res($k$) propositional proof system does not have the weak feasible disjunction property. Next, we generalize a recent result of Atserias and Müller [FOCS, 2019] to Res($k$). We show that if NP is not included in P (resp. QP, SUBEXP) then for every integer $k \geq 1$, Res($k$) is not automatable in polynomial (resp. quasi-polynomial, subexponential) time.

at March 21, 2020 11:53 AM UTC

Greetings from the future! The progression of covid-19 in Italy is running about eight days ahead of France and Spain and about 16 days ahead of the United States. Here in Lombardy, which is about ten days ahead of NYC, we have been “sheltering at home” for 13 days already.

How is social distancing working out for me? I thought that I was well prepared for it, but it is still not easy. I have started to talk to the furniture, and apparently this is perfectly normal, at least as long as the furniture does not talk back.

As I have been telling my dining table, it has been very dismaying to read news from the US, where there seemed to be a very dangerous complacency. I am relieved to see that this is changing, especially at the state level, which makes me much more hopeful.

I have also found media coverage to be disappointing. Apparently, many highly educated people, including people whose job involves understanding policy issues, have no idea how numbers work (source). This is a problem because a lot of issues concerning this epidemic have to do with numbers, which can be misleading if they are not reported in context.

For example, before the time when Trump decided that he had retroactively been concerned about a pandemic since January, conservative media emphasized the estimate of a 2% mortality rate, in a way that made it sound, well, 98% of people survive, and 98% is approximately 100%, so what is the big deal. For context, the Space Shuttle only exploded 1.5% of the times, and this was deemed too dangerous for astronauts. This is the kind of intuitive reference that I would like to see more of.

Even now, there is a valid debate on whether measures that will cost the economy trillions of dollars are justified. After all, it would be absurd to spend trillions of dollars to save, say, 10,000 lives, it would be questionable to do so to save 100,000 lives, and it would be undoubtedly right to do so to save millions of lives and a collapse of the health care system (especially considering that a collapse of the health care system might create its own financial panic that would also cost trillions of dollars).

So which one is it? Would doing nothing cost 10,000 American lives? A million? How long will people have to “shelter at home”? And what is next? I can recommend two well-researched articles: this on plausible scenarios and this on what’s next.

Kristof’s article cites an essay by Stanford professor John Ioannidis who notes that it is within the realm of possibilities, given the available data, that the true mortality rate could be as low as 0.05%, that is, wait for it, lower than the mortality rate of the flu. Accordingly, in a plausible scenario, “If we had not known about a new virus out there, and had not checked individuals with PCR tests, the number of total deaths due to “influenza-like illness” would not seem unusual this year.”

Ioannidis’ essay was written without reference to data from Italy, which was probably not available in peer-reviewed form at the time of writing.

I would not want professor Ioannidis to tell me how to design graph algorithms, and I don’t mean to argue for the plausibility of the above scenario, but let me complement it with some data from Italy.

Lombardy is Italy’s richest and most developed region, and the second richest (in absolute and PPP GDP) administrative region in Europe after the Ile de France (source). It has a rather good health care system. In 2018, on average, 273 people died per day in Lombardy of all causes (source). Yesterday, 381 people died in Lombardy with coronavirus (source). This is spread out over a region with more than 10 million residents.

Some areas are harder-hit hotspots. Three days ago, a Bergamo newspaper reported that 330 people had died in the previous week of all causes in the city. In the same week of March in 2019, 23 people had died. That’s a 14x increase of mortality of all causes. Edited to add (3/22/2020): the mayor of Bergamo told Reuters that 164 people died in Bergamo of all causes in the first two weeks of March 2020, versus 56 in the first two weeks of March 2019, a 3x increase instead of the 14x increase reported by Bergamo News.

Bergamo’s hospital had 16 beds in its intensive care unit, in line with international standards (it is typical to have of the order of an ICU bed per 5000-10,000 people, and Bergamo has a population of 120,000). Right now there are 80 people in intensive care in Bergamo, a 5x increase in capacity that was possible by bringing in a lot of ventilators and moving other sick people to other hospitals. Nonetheless, there have been reports of shortages of ICU beds, and of people needing to intubated that could not be. There are also reports of people dying of pneumonia at home, without being tested.

Because of this surge in deaths, Bergamo’s funeral homes have not been able to keep up. It’s not that they have not been able to keep up with arranging funerals, because funerals are banned. They just do not have the capacity to perform the burials.

So coffins have been accumulating. A couple of days ago, a motorcade of army vehicles came to Bergamo to pick up 70 coffins and take them to other cities.

It should be noted that this is happening after 20 days of “social distancing” measures and after 13 days of “sheltering at home” in Lombardy.

My point being, if we had not known that a news virus was going around, the number of excess deaths in Bergamo would have not been hidden by the random noise in the number of deaths due to influenza-like illness.

by luca at March 20, 2020 07:37 PM UTC

On the behalf of the organizers, I am excited to announce that the next Simons workshop Lattices: New Cryptographic Capabilities will take place next week Mar 23-27, 2020 over Zoom!

The workshop will cover advanced lattice-based cryptographic constructions, while also highlighting some of the recurring themes and techniques, reiterated through a game of Bingo! The rest of this post provides a sneak preview along with the Bingo puzzle.

Looking forward to seeing everyone at the workshop!

Hoeteck, together with Shweta, Zvika and Vinod

Zoom Guidelines/Tips

  • To ask a question, use the “raise hand” feature.
  • If the speaker’s slide is not displaying in its entirety, try “side-by-side mode” under “view options”.
  • Please log in to Zoom with your full name.

A Sneak Preview

Let A1, A2 be square matrices and t a row vector such that

tA1 = x1t, tA2 = x2t
Using high-school algebra lingo, we would refer to t as the eigenvector of A1, A2. It is easy to see that

t ⋅ (A1 + A2) = (x1 + x2)t, t ⋅ A1A2 = x1x2t
This extends readily to any polynomial p(x1, …, xn), namely: if tAi = xit, then

t ⋅ f(A1, …, An) = f(x1, …, xn)t
As in turns out, much of advanced lattice-based crypto boils down to a generalization of this statement! The generalization is along two orthogonal dimensions:

  1. arbitrary matrices A1, …, An that may not share the same eigenvector t, and
  2. a relaxation to “approximate” equality, namely tAi ≈ xit.

The generalization underlies fully homomorphic encryption, homomorphic signatures, attribute-based encryption schemes and many more!


Here’s the 4×4 bingo puzzle:

GGH15 Bonsai AR+G noise growth
G − 1 LWE Vinod LHL
Gaussian Af FHE Dec linear noise flooding
homomorphic trapdoor smoothing parameter Hf, x

by Hoeteck Wee at March 20, 2020 03:07 PM UTC

From Sandy Irani, FOCS 2020 PC chair:

In light of the very unusual developments in the world due to the spread of Covid-19 and the disruption it is causing to many people in our field, especially those with young children at home, the FOCS PC has decided to push back the final deadline for papers by six days. We would have liked to do more, but we still are trying to stick to our timeline for notification since that date is coordinated with other deadlines in the theory community. In addition, some members of the committee are also affected by this crisis and there is concern that we may not be able to do our job as a committee in a shorter time frame. Pre-registration (including titles and abstracts) is still required by the original deadline. Here are the new dates:

Pre-registration (including titles and abstracts): Thursday April 9, 11:59 PM (EDT)

Final Paper Submission: Wednesday April 15, 11:59 PM (EDT)

Conference url:

We hope you all stay healthy!

–Sandy Irani, for the FOCS 2020 Committee

by Boaz Barak at March 19, 2020 04:27 PM UTC

First of all both the Turing award and Abel Prize announced yesterday.

As we start moving from the panic phase of the coronavirus to the boring phase, what kinds of things should you do or not do while stuck at home for the next two weeks to eighteen months.

First of all still do your job. Teach your online classes. Try to do some research. Meet with your colleagues/students/advisor virtually (best with Zoom or something similar). Submit to conferences. What else? Use the situation for your advantage.

Attend virtual conferences: Really attend. Pretend that you flew there and devote the entire day to going to virtual talks or chatting with other attendees in virtual hallways. I said it wouldn't happen this way last week so prove me wrong.

Create a Virtual Workshop: Because you can. Invite people to give online talks. Open it up for all to listen. Find ways to discuss together.

Connect: Make a virtual get-together with an old colleague or someone you've always wanted to meet. Researchers around the world will be holed up and happy to get some interactions.

Learn Something New: Read a textbook. Take an online course in CS or something completely different. There are plenty.

Help Others Learn: Start that book you've always wanted to write. Or just write a short survey article giving your view of a slice of the theory world. Create some videos or a podcast to explain stuff.

Pick up a hobby: Something outside computer science just to keep your sanity.

Watch some fun computer-related movies: Her, Sneakers, The Computer wore Tennis Shoes, 2001, The Imitation Game, Hidden Figures, Colossus: The Forbin Project, Ex Machina. Add your own favorites in the comments.

And on the other hand don't

Become an epidemiologist: As a computer scientist you are an expert in networks, graph theory and exponential growth so you can create models that show we are grossly under preparing and/or overreacting to the virus and want to tell the world how you are right and the so-called "experts" are wrong. Please don't.

Prove P ≠ NP: Trying to settle P v NP and failing is instructive. Trying to settle P v NP and thinking you succeeded is delusional.

Freak Out: We will get past this virus and the world will recover.

Bill will follow up with his own ideas in part II next week.

by Lance Fortnow ( at March 19, 2020 01:45 PM UTC

The second Foundations of Data Science virtual talk will take place next Friday, March 27th at 11:00 AM Pacific Time (2:00 pm Eastern Time, 20:00 Central European Time, 19:00 UTC).  Sujay Sanghavi from University of Texas at Austin will speak about “Towards Model Agnostic Robustness”.

Abstract: It is now common practice to try and solve machine learning problems by starting with a complex existing model or architecture, and fine-tuning/adapting it to the task at hand. However, outliers, errors or even just sloppiness in training data often lead to drastic drops in performance.

We investigate a simple generic approach to correct for this, motivated by a classic statistical idea: trimmed loss. This advocates jointly (a) selecting which training samples to ignore, and (b) fitting a model on the remaining samples. As such this is computationally infeasible even for linear regression. We propose and study the natural iterative variant that alternates between these two steps (a) and (b) – each of which individually can be easily accomplished in pretty much any statistical setting. We also study the batch-SGD variant of this idea. We demonstrate both theoretically (for generalized linear models) and empirically (for vision and NLP neural network models) that this effectively recovers accuracy in the presence of bad training data.

This work is joint with Yanyao Shen and Vatsal Shah and appears in NeurIPS 2019, ICML 2019 and AISTATS 2020.

Link to join the virtual talk.

The series is supported by the NSF HDR TRIPODS Grant 1934846.

by dstheory at March 19, 2020 02:29 AM UTC

Machine learning on big data sets takes a significant amount of computational power, so it is often necessary to offload some of the work to external distributed systems, such as an Amazon EC2 cluster. It is useful to be able to utilize external resources for computation tasks while keeping the actual data private and secure. In particular, matrix multiplication is an essential step in many machine learning processes, but the owner of the matrices may have reasons to keep the actual values protected.

In this post, we’ll discuss four works about secure distributed computation. First, we’ll talk about a method of using MDS (maximum distance separable) error correcting codes to add security and privacy to general data storage (“Cross Subspace Alignment and the Asymptotic Capacity of X-Secure T-Private Information Retrieval” by Jia, Sun, Jafar).

Then we’ll discuss method of adapting a coding strategy for straggler mitigation (“Polynomial codes: an optimal design for high-dimensional coded matrix multiplication” by Yu, Qian, Maddah-Ali, Avestimehr) in matrix multiplication to instead add security or privacy (“On the capacity of secure distributed matrix multiplication” by Chang, Tandon and “Private Coded Matrix Multiplication” by Kim, Yang, Lee)

Throughout this post we will use variations on the following communication model:

The data in the grey box is only given to the master, so workers only have access to what they receive (via green arrows). Later on we will also suppose the workers have a shared library not available to the master. The workers do not communicate with each other as part of the computation, but we want to prevent them from figuring out anything about the data if they do talk to each other.

 This model is related to private computation but not exactly the same. We assume the servers are “honest but curious”, meaning they won’t introduce malicious computations. We also only require the master to receive the final result, and don’t need to protect any data from the master. This is close to the BGW scheme ([Ben-Or, Goldwasser, Wigderson ’88]), but we do not allow workers to communicate with each other as part of the computation of the result.

 We consider unconditional or information-theoretic security, meaning the data is protected even if the workers have unbounded computational power. Furthermore, we will consider having perfect  secrecy, in which the mutual information between the information revealed to the workers and the actual messages is zero.

X-Secure T-Private Information Retrieval

 Before we get into matrix-matrix multiplication, consider the problem of storing information on the workers to be retrieved by the master, such that it is “protected.” What do we mean by that? [Jia, Sun, and Jafar ’19] define X-secure T-private information retrieval as follows:

Let W_1,...,W_{K} be a data set of messages, such that each W_i consists of L random bits. A storage scheme of W_{1},...,W_{K} on N nodes is 

1. X-secure if any set of up to X servers cannot determine anything about any W_i and

2. T-private  if given a query from the user to retrieve some data element W_{\theta}, any set of up to T users cannot determine the value of \theta.

[Jia, Sun, and Jafar ’19]

Letting Q_{1}^{[\theta]},...,Q_{N}^{[\theta]} be the set of queries sent to each node and S_1,...,S_N be the information stored on each node (all vectors of length L), we depict this as:

The information theoretic requirements of this system to be correct can be summarized as follows (using notation S_{[1:N]} for set S_1,...,S_N):

PropertyInformation Theoretic Requirement
Data messages are size L bitsH(W_1)=H(W_2)=....=H(W_K) = L
Data messages are independentH(W_1,...,W_K) = KL
Data can be determined from the stored informationH(W_1,....,W_K)|S_{[1:N]}) = 0
User has no prior knowledge of server dataI(S_{[1:N]};Q^{[\theta]}_{[1:N]},\theta) = 0
X-SecurityI(S_{\mathcal{X}};W_1,...,W_K) = 0, \forall \mathcal{X}\subset [1:N],|\mathcal{X}|=X
 T-PrivacyI(Q_{\mathcal{T}}^{[\theta]},S_{\mathcal{T}}; \theta) = 0,  \forall \mathcal{T} \subset [1:N], |\mathcal{T}|=T
Nodes answer only based on their data and received query H(A_n^{[\theta]}| Q_n^{[\theta]},S_n) =0
User can decode desired message from answersH(W_{\theta} | A_{[1:N]}^{[\theta]},Q_{[1:N]}^{[\theta]} ,\theta) = 0

Given these constraints, Jia et al. give bounds on the capacity of the system. Capacity is the maximum rate achievable, where rate is defined as bits requested by the worker (L, the length of a single message) divided by the number of bits downloaded by the worker. The bounds are in terms of the capacity of T-Private Information Retrieval, (which is the same as the above definition, with only requirement 2).

If N \leq X+T then for arbitrary K, C_{XSTPIR}(N,K,X,T) = \frac{N-X}{N}C_{TPIR}(N-X,K,T) = \frac{N-X}{NK}.

\displaystyle C_{XSTPIR}(N,K,X,T) \leq \left(\frac{N-X}{N}\right) C_{TPIR}(N-X,K,T)

When N\leq X+T: \displaystyle C_{XSTPIR}(N,K,X,T) = \left(\frac{N-X}{N}\right) C_{TPIR}(N-X,K,T) = \frac{N-X}{NK}

 \displaystyle\lim_{K\to \infty} C_{XSTPIR}(N,K,X,T) = \lim_{K\to \infty} \left(\frac{N-K}{N}\right) C_{TPIR}(N-X,K,T) =\begin{cases}   1-(\frac{X+T}{N}) & N>X+T  \\   0 & N\leq X+T \end{cases}

[Jia, Sun, and Jafar ’19]

Jia et al. give schemes that achieve these bounds while preserving the privacy and security constraints by introducing random noise vectors into how data is stored and queries are constructed. The general scheme for N>X+T uses cross subspace alignment, which essentially chooses how to construct the stored information and the queries such that the added noise mostly “cancels out” when the master combines all the response from the servers. The scheme for N\leq X+T is straightforward to explain, and demonstrates the idea of using error correcting codes that treat the random values as the message and the actual data as the “noise.”

For this scheme, the message length L is set to N-X (the number of nodes N, minus the maximum number of colluding servers X). First, we generate K random bit vectors of length X:

Next, apply an (N,X) MDS code to Z_1,...,Z_K to get \bar{Z}_1,..,\bar{Z}_K, which are K encoded vectors of length N:

For our data W_1,...,W_K, we pad each vector with zeros to get \bar{W}_1,..,\bar{W}_K of length N:

Now that the dimensions line up, we can add the two together and store each column n at the n^{th} node:

To access the data, the user downloads all NK bits. The length N string downloaded from  row i can be used to decode \bar{Z}_i: \bar{W}_{L+1},\bar{W}_{L+2},...,\bar{W}_{N} are all zero, so columns L+1 = N-X+1 through N have the values of \bar{Z}_{i,N-X+1},...,\bar{Z}_{i,N}. This gives the user X values from the MDS code used on each row, so they can decode and get Z_1,...,Z_K and \bar{Z}_{1},...,\bar{Z}_K. Then a subtraction from the downloaded data gives W_1,...,W_{K}. Because of the MDS property of the code used to get \bar{Z}_1,...,\bar{Z}_K, this scheme is X-secure and because the user downloads all bits, it is T-private.

Matrix Multiplication with Polynomial Codes

We now move on to the task of matrix-matrix multiplication. The methods for secure and private distributed matrix multiplication we will discuss shortly are based on polynomial codes, used by [Yu, Maddah-Ali, Avestimehr ’17] for doing distributed matrix multiplications robust to stragglers. Suppose the master has matrices {\bf{A}} \in \mathbb{F}_q^{m\times n} and {\bf{B}} \in \mathbb{F}_q^{n \times p} for some finite field \mathbb{F}_q, and m,n,p \in \mathbb{Z}^+. Assume m and p are divisible by N, so we can represent the matrices divided into N submatrices:

{\bf{A}}= \begin{bmatrix}A_1\\ A_2 \\ \vdots \\ A_m\end{bmatrix} and {\bf{B}}= \begin{bmatrix}B_1& B_2 & \dots &B_n\end{bmatrix}

So to recover \bf{AB}, the master needs each entry of:

{\bf{AB}} = \begin{bmatrix}A_1B_1 & A_1B_2 & \dots & A_1B_n\\A_2B_1 & A_2B_2 & \dots & A_2 B_n\\\vdots & \vdots &\vdots &\vdots\\A_mB_1 &A_mB_2 & \dots  & A_mB_n \end{bmatrix}.

The key idea of polynomial codes is to encode A_1,...,A_m and B_1,...,B_n in polynomials \tilde{A}_i and \tilde{B}_i to be sent to the i^{th} worker,  where they are multiplied and the result is returned. The goal of Yu et al. was to create robustness to stragglers, and so they add redundancy in this process so that not all workers need to return a result for the master to be able to determine \bf{AB}. In particular, only mn returned values are needed, so N-mn servers can be slow or fail completely without hurting the computation. This method can be thought of as setting up the encodings of \bf{A} and \bf{B} so that the resulting multiplications \tilde{C}_1=\tilde{A}_1\tilde{B}_1,...,\tilde{C}_N=\tilde{A}_N\tilde{B}_N are evaluations of a polynomial with coefficients  A_1B_1,A_1B_2,...,A_2B_1....,A_mB_n at N different points — equivalent to a Reed-Solomon code. 

This idea is adapted by [Chang, Tandon ’18] to protect the data from colluding servers: noise is incorporated into the encodings such that the number of encoded matrices required to determine anything about the data is greater than the security threshold X < N. Since the master receives all N responses it is able to decode the result of \textbf{AB}, but no set of X nodes can decode \textbf{A}, \textbf{B}, or \textbf{AB}. Similarly, [Kim, Yang, Li ’19] adapts this idea to impose privacy on a matrix-matrix multiplication: workers are assumed to have a shared library \{{\textbf{B}}_i\}_{i=1}^M, and the user would like to multiply {\textbf{A}}{\textbf{B}}_{D} for some D \in[1:M] without revealing the value of D to the workers. The workers encode the entire library such that when the  encoding is multiplied by an encoded input \tilde{A} from the master, the result is useful to the master in decoding {\textbf{A}}{\textbf{B}}_D.

Chang and Tandon consider the following two privacy models, where up to \ell servers may collude. The master also has K^{(A)} (and in the second model, K^{(B)}), which are matrices of random values with the same dimensions as \textbf{A} (and \textbf{B}). These are used in creating the encodings \tilde{A}_i (and \tilde{B}_i).

 \textbf{B} is public, \textbf{A} is private:

Both private:

Kim, Yang, and Lee take a similar approach of applying the method of polynomial code to private matrix multiplication. As before, there are N workers, but now the master wants to multiply \textbf{A} with some {\textbf{B}}_D in shared library \{{\textbf{B}}_i\}_{i=1}^M (all the workers have the shared library). 

Since the master isn’t itself encoding \{{\textbf{B}}\}_{i=1}^M it has to tell the workers how to encode the library so that it can reconstruct the desired product. This is done by having the master tell the workers what values of \vec{y} they should use to evaluate the polynomial that corresponds to encoding each library matrix. We denote the encoding of the library done by each worker i as the multivariate polynomial h which is evaluated at \{{\textbf{B}}\}_{i=1}^M and the node-specific vector y^{(i)}_{[1:M]} to get the node’s encoding, \tilde{B}_i. The worker multiplies this with the encoding of \textbf{A} it receives, \tilde{A}_i and returns the resulting value Z_i. All together, we get the following communication model: 


As we’ve seen, coding techniques originally designed to add redundancy and protect against data loss can also be used to intentionally incorporate noise for data protection. In particular, this can be done when out-sourcing matrix multiplications, making it a useful technique in many data processing and machine learning applications.


by Alex Porter at March 18, 2020 11:14 PM UTC

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.


by plustcs at March 18, 2020 11:13 PM UTC

So far, I confess, this pandemic is not shaping up for me like for Isaac Newton. It’s not just that I haven’t invented calculus or mechanics: I feel little motivation to think about research at all. Or to catch up on classic literature or films … or even to shower, shave, or brush my teeth. I’m quarantined in the house with my wife, our two kids, and my parents, so certainly there’s been plenty of family time, although my 7-year-daughter would inexplicably rather play fashion games on her iPad than get personalized math lessons from the author of Quantum Computing Since Democritus.

Mostly, it seems, I’ve been spending the time sleeping. Or curled up in bed, phone to face, transfixed by the disaster movie that’s the world’s new reality. Have you ever had one of those nightmares where you know the catastrophe is approaching—whether that means a missed flight, a botched presentation at your old high school, or (perhaps) more people dying than in any event since WWII—but you don’t know exactly when, and you can do nothing to avert it? Yeah, that feeling is what I now close my eyes to escape. And then I wake up, and I’m back in bizarro-nightmare-land, where the US is in no rush whatsoever to test people or to build ventilators or hospitals to cope with the coming deluge, and where ideas that could save millions have no chance against rotting institutions.

If nothing else, I guess we now have a decisive answer to the question of why humanity can’t get its act together on climate change. Namely, if we can’t wrap our heads around a catastrophe that explodes exponentially over a few weeks—if those who denied or minimized it face no consequences even when they’re dramatically refuted before everyone’s eyes—then what chance could we possibly have against a catastrophe that explodes exponentially over a century? (Note that I reject the view that the virus was sent by some guardian angel as the only possible solution to climate change, one crisis cancelling another one. For one thing, I expect emissions to roar back as soon as this new Black Death is over; for another, the virus punishes public transportation but not cars.)

Anyway, I realized I needed something, not necessarily to take my mind off the crisis, but to break me out of an unproductive spiral. Also, what better time than the present for things that I wouldn’t normally have time for? So, continuing a tradition from 2008, 2009, 2011, 2013, 2015, and 2018, we’re going to do an Ask Me Anything session. Questions directly or tangentially related to the crisis (continuing the discussion from the previous thread) are okay, questions totally unrelated to the crisis are even okayer, goofball questions are great, and questions that I can involve my two kids in answering are greatest of all. Here are this year’s ground rules:

  • 24 hours or until I get bored
  • One question per person total
  • Absolutely no multi-part questions
  • Self-contained questions only—nothing that requires me to read a paper, watch a video, etc.
  • Scan the previous AMAs to see if your question is already there
  • Any sufficiently patronizing, hostile, or annoying questions might be left in the moderation queue, 100% at my discretion

So ask away! And always look on the bright side of life.

Update (March 19): No more questions, please. Thanks, everyone! It will take me a few days just to work through all the great questions that are already in the queue.

Update (March 24): Thanks again for the 90-odd questions! For your reading convenience, here are links to all my answers, with some answers that I’m happy with bolded.

by Scott at March 18, 2020 09:02 PM UTC

Barak Weiss lectured about his breakthrough results with Or Ordentlich, and Oded Regev, at a Simons Institute workshop: Lattices: Geometry, Algorithms and Hardness.

It is a famous problem what is the densest (or, most efficient) packing of unit balls in Euclidean n-dimensional spaces and, of course, you can ask the same questions for other convex bodies. A sort of a dual problem, also famous, is the question of the most efficient covering the n-dimensional Euclidean space by balls or by translates of other convex bodies.

A very basic insight is that covering is much more efficient than packing. Can you explain the reason for that? The only thing that came up to my mind was that convex sets are roundish from the outside but not from the inside which makes it easier to cover with them.

But how efficiently can we cover the n-dimensional Euclidean space with translates of a convex body $K$?

C.A. Rogers with coauthors had some very fundamental results regarding covering (and packing) in the 50s and 60s. Or Ordentlich, Oded Regev and Barak Weiss have made a terrific improvement for one of the main questions in this area. They showed that for every convex set K, you can find a lattice of determinant 1, and r>0  such that rK+L = \mathbb R^n and

{\rm vol} (rK) \le cn^2.

The best earlier upper bound was n^{\log \log n}.

One surprising aspect of the proof is the use of finite field Kakeya-type questions. Since the breakthrough by Zeev Dvir, many people had hopes for applications from the finite fields results to the Euclidean setting (in particular, to the Euclidean Kakeya problem itself) and it is rare to see such applications. The proof here relies on results by  Dvir, Kopparty, Saraf, Sudan, and Lev. The Ordentlich-Regev-Weiss paper is not yet on the arXiv but the lecture gives a good picture about the results and the proofs.

The definition of the covering density of L with respect to a convex body K

The definition of the covering density of K

Old results for the Euclidean ball

Old results for general convex bodies

The first main result


The required finite field Kakeya theorem.

by Gil Kalai at March 18, 2020 10:39 AM UTC

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!

by plustcs at March 18, 2020 12:01 AM UTC

Stay safe, everyone

Cropped from Floss Dance source

Neil L. is a Leprechaun. He has visited me once every year since I started GLL. I had never seen a leprechaun before I began the blog—there must be some connection.

Today, Ken and I want to share the experiences we had with him on this morning of St. Patrick’s Day.

I thought because of the pandemic that he might not come. I thought that since New York City is on virtual lock-down he might not come. So I decided not to wait up for his visit, which always occurs in the wee hours of the morning. I looked it up: Wee hours is between 1am and 4am. We—that is Kathryn and I not wee—went to bed before midnight.

Something woke me up at 3am. Not any noise but a bright green light. It was coming from my laptop, which was on the dresser but closed and switched off. I took it out of the bedroom and opened the lid and there he was.

Top o’ the morning to ye.

Neil Says Hi

The first thing I noticed was: no pipe. There was no puff of smoke in my living room. Neil smokes a special brand of tobacco—green of course—that I would recognize in an instant. Otherwise he looked as usual: green coat and hat, brown vest and shoes, red beard. I could see all of him.

“Glad as always to see you Neil. But why no pipe?”

Neil started his usual pipe-puffing gesture but stopped his hand from touching his face.

‘Tis virus not microbe. Smoke nae gan do good. All of us doing without. Least of our troubles.

Wow—that was hard for me to fathom. I thought of the travel bans. “Are you all having to stay home?”

Aye. We obey the bans. Crown or Republic, nae matter.

I had to wrap my mind around this—leprechauns too? “The virus applies to you?”

Sadly, we can carry it. Were it not, we could help folks point-to-point.

I realized: leprechauns can go anywhere instantly. The planar aspects of simulations like this do not apply to them. Neil read my mind—at least he could do that remotely:

Aye. I noted all your comment thread about expander graphs and spreading the disease. Fixed dimensions don’t constrain us. This compounds our main trouble, which be…

Of course our main trouble and concern is the danger of the virus—our being able to care for those who catch it and measures to ensure many do not catch it. I realize leprechauns, being immortal, have fewer worries there—and I did not ask Neil if they can get sick. So I thought of all the canceled St. Patrick’s Day parades, bars closing, no public merriment, sporting events gone too. But Neil’s next word went straight to the heart.


Boredom and Randomness

I thought about fun things Neil had recounted in the past: tricks with math and codes and logic, tricks on people, even tricks during March Madness. The NCAA tournament got completely canceled, unpostponable. Neil read my mind again and picked up on the topic of sporting events.

Consider me neighbor Bertie. He had his accommodations booked on the wee island in the pond of the 17th hole at TPC Sawgrass. For last weekend during the Players Championship. That’s why they built the island, ye know.

“The Purest Test in Golf” source

But of course, the Players was canceled. Even the Masters has been postponed. Neil continued,

He and his fellows’ best craic was playing with the balls goon o’er the water. Not in a nasty way. Ye know by the Rule of Indistinguishability we canna do them bad. Not allowed to make them play worse than other tough holes so ye could tell it is more than the usual hobgoblins in your head and butterflies in your chest. What we do must have the same expectation and other moments as random variation. But random is measure-1 so it is easy to comply.

Of course. We have written about feigned randomness, and we haven’t yet had time to write a post this year on scientists taking superdeterminism seriouslyeven computationally. How could we tell that stuff apart from leprechauns? But thinking of Bertie gave me a more obvious question:

“Neil, can’t Bertie and his pals do that remotely? Like lots of other things we’re doing now.”

Neil’s answer exposed my lack of basic leprechaun knowledge.

In every story of leprechaun tricks, who is present? The leprechaun. He cannot be remote—and he must run the risk of being catched. He can dance, run to the end of the rainbow, and disappear, but fun happens only when he is around.

Hearing this, I would have puffed my own pipe, if I smoked and had one. Neil continued:

Besides, remotely we cannot control well enough to abide the Rule of Indistinguishability.

All this about randomness and conspiracy physics, with the world already weighing heavily, was too much. I winked out on the couch, without closing my laptop or seeing if Neil said goodbye with his usual flourish.

I woke up in late morning and called Ken. As I told this part, Ken was instantly alarmed and horrified.

“We must get Neil back. Is he still on your laptop?”

He was not. Ken plugged in and opened his own laptop—Neil has in the past visited him too—but nothing. He could not find any leprechauns registered on Skype or Zoom or Hangouts. Then Ken had a thought: “See if your laptop has the IP records.”

It did. I could not tell what they signified, but my old IT contact at Tech said he could pinpoint the origin in minutes. Meanwhile, Ken calmed down enough to explain. I’ll let him write the rest of the story.

The One Uncanceled Competition

What is apparently the lone major human sporting competition in the world not to be canceled began today. It is chess—the Candidates Tournament to determine who will face Magnus Carlsen in the next world championship match. It is taking place in Yekaterinburg, Russia—in Siberia, still far from the worst virus activity. It has only the 8 players plus officials onsite—no spectators, press limited—and they are all subject to daily screenings. The players shake hands only virtually.

Controversy about its starting continued today with one former World Champion, Vladimir Kramnik, stepping down from a broadcast commentary team “considering the nowadays disastrous humanitarian situation in the world.” But I’m with those saying that its value as a diversion—something to follow live in community—outweighs the concerns. I said this after some reflection on risks from our previous post and before being contacted about monitoring the tournament. One Chinese broadcast had over 1 million viewers today. Other broadcasts can be found on the official site and several other places. Today’s first round was vigorous, with all four games going beyond the turn-40 time control and two decisive.

But if it is a lone attraction for us, omigosh, for the leprechauns… Dick’s story proved they can at least read minds remotely. What if they all banded together to mess with the players’ moves? Neil had told of the Indistinguishability constraint, but I realized my own work could enable getting around it. My model enables randomly simulating a human distribution of moves at any rating level. I’ve had the idea to try a “Turing Test” akin to one Garry Kasparov turned aside, as part of the Turing Centennial in 2012, by distinguishing five games played by human 2200-level players from five by computers set to play at 2200 strength. If the leprechauns passed the Turing test at a 2800 rating level they could derange the tournament. This all verges on real concerns in my statistical anti-cheating work, with humans not leprechauns.

I quickly looked up the lore for summoning a leprechaun. This is far more audacious than knocking on a professor’s door outside office hours—not that that will happen anytime soon. I did not have real shamrocks but strewed countryside photos from my family’s trip to Ireland last summer around my laptop. I needed Kathryn as well as Dick online by videoconference to make the quorum of three. The IT person came back with the coordinates so that uniquely Neil would be summoned. I adapted the ancient incantation to our new age of interaction by laptop:

Oh Leprechaun, Leprechaun, I humbly call unto thee,
Ride the Irish rainbows of joy across the virtual sea,
Let the cables be lit with the beacon of your Shillelagh,
In dire peril of bad luck I make this plea,
For an unknown evil lies near, I ween:
Oh Leprechaun, Leprechaun, please appear on my screen!

It worked. Neil crackled into view. After a short greeting I blurted out my concerns.

Nae worry. Nae worry. The International Chess Federation—FIDE—took the most important step to assure the fair play.

Wait—I know the fair-play measures FIDE developed. I’ve been part of them. That didn’t assuage what I’d just said.

FIDE put not just one but two Scotsmen on the tournament staff. One of them is in charge of fair play. Nae Leprechaun gan cross a Scotsman!

And with that Neil was gone.

Open Problems

Our hearts go out to all those affected more immediately than we so far. Amid all the worries, we wish you a happy and safe St. Patrick’s Day.

[some formatting and wording tweaks]

by RJLipton+KWRegan at March 17, 2020 10:58 PM UTC

Richard Guy passed away on March 9, 2020 at the age of 103. Before he died he was the worlds oldest living mathematician (see here for a list of centenarians who are famous scientists or mathematicians). He was also the oldest active mathematician-- he had a paper on arxiv (see here) in October of 2019.  (ADDED later since a commenter pointed it out to me--- a paper by Berlekamp and Guy posted in 2020: here)

I met him twice- once at a Gathering for Gardner, and once at an AMS meeting. I told him that Berlekamp-Conway-Guy had a great influence on me. He asked if it was a positive or negative influence. He also seemed to like my talk on The Muffin Problem, though he might have been being polite.

I did a blog about Richard Guy on his 103rd birthday, so I recommend readers to go there
for more about him.  One point I want to re-iterate:

Richard Guy thought of himself of an amateur mathematician. If he means someone who does it for love of the subject then this is clearly true.  If it is a measure of how good he is (the term `amateur' is sometimes used as an insult) then it is clearly false. If it means someone who does not have formal training than it is partially true.

by GASARCH ( at March 17, 2020 04:43 PM UTC

Looks like we’ll all be seeing a long time at home with little to do but go online. So here is my usual update of links I recently found interesting. (I’m deliberately not linking Coronavirus information, despite its importance, both because I’m not an expert and have neither useful original opinions to contribute nor adequate filters between information and misinformation, and because I suspect that many people’s mental health depends on not getting overloaded with that stuff while there’s so little to do but staying isolated and avoiding becoming part of the problem).

by David Eppstein at March 15, 2020 04:40 PM UTC