On twelve STOC'19 presentations

Here is a list of STOC19 papers that I found interesting. As usual, some omissions are due to my not attending the relevant talks due to conflicts with other sessions or other considerations. Some of the following works were already reviewed in prior choices of mine, in which case I only provide a pointer. For the others, some comments follow.

  1. Bootstrapping Results for Threshold Circuits Just Beyond Known Lower Bounds by Lijie Chen and Roei Tell [see Choice 256]
  2. The Log-Approximate-Rank Conjecture is False by Arkadev Chattopadhyay, Nikhil Mande, and Suhail Sherif
  3. Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme by Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
  4. Distributed Edge Connectivity in Sublinear Time by Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak
  5. Towards the Locality of Vizing's Theorem by Hsin-Hao Su and Hoa T. Vu
  6. Testing Graphs against an Unknown Distribution by Lior Gishboliner and Asaf Shapira
  7. Testing Unateness Nearly Optimally by Xi Chen and Erik Waingarten
  8. Random walks and forbidden minors II: a poly(d/epsilon)-query tester for minor-closed properties of bounded degree graphs by Akash Kumar, C. Seshadhri, and Andrew Stolman [see Choice 263]
  9. Static Data Structure Lower Bounds Imply Rigidity by Zeev Dvir, Alexander Golovnev, and Omri Weinstein
  10. Solving Linear Programs in the Current Matrix Multiplication Time by Michael Cohen, Yin Tat Lee, and Zhao Song
  11. Sylvester-Gallai type theorems for quadratic polynomials by Amir Shpilka
  12. Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes by Dylan McKay, Cody Murray, and Ryan Williams
Before commenting on the foregoing works, let me make a few comments about the non-program aspects of this conference.

FCRC: I think the only prior FCRC that I have attended was the one held in 2007 in San Diego. I vaguely recall that I did not like it, but don't recall it as so traumatic as the current one. It felt like being in some monstrous commercial fair, something that does not align with my expectations of the experience of attending a scientific conference. Putting my personal experience aside, I fail to see any good rational for having STOC ``participate'' in FCRC (or rather be ``swallowed'' by it, let alone the high registration fee). Co-locating STOC with some specialized TOC conferences, as done in the theory fest, does make sense, since it contributes to the unity of TOC and consolidates it as well as saves us some travel. None of these holds wrt FCRC, and I hope that STOC will stop taking part in FCRC.

Phoenix in June: One artifact of being part of FCRC is being subjected to their weird choices. One must be out of their mind to hold a conference under such weather conditions. I guess humans can endure such weather conditions and even worse ones, but why choose to do so? Why call upon people from all over the world to travel to one of the least comfortable locations (per the timing)?

The senior-junior lunches: To end this part with a positive note, let me commend whoever is responsible for the initiation and organization of these mutually empowering encounters called senior-junior lunches. I do not like the framing of these lunches as `networking' (and I'm not a great believer in this notion when applied to the scientific community); I think of these lunches as general tutoring sessions, where by `general' I mean that their focus is (or should be) on general aspects of doing research in TOC. In addition to consulting the more juniors on whatever interests them, I think that these sessions empower them by revealing to them that their questions are almost always fundamental ones, rooted in the objective realities of (theoretical) research in general. The seniors are also empowered by feeling the keen interest of a new generation.

The Log-Approximate-Rank Conjecture is False by Arkadev Chattopadhyay, Nikhil Mande, and Suhail Sherif

The log-rank conjecture has always struck me as highly implausible, but from that perspective it is a begging challenge to refute it and its various variants, let alone that such refutations are likely to contribute to our understanding of the area. The current work refutes the straightforward adaptation of the conjecture to randomized communication complexity.

Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme by Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai

What captured my attention is this work is the use of local exploration (akin Property Testing and Local Computation Algorithms) in the context of standard graph algorithms.

Distributed Edge Connectivity in Sublinear Time by Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak

This work present the first sublinear-time algorithm for distributively computing the (exact) edge connectivity of a network in the CONGEST model. The round complexity is sublinear for any value of the diameter of the network (as long as there are no parallel edges). The work uses an expander decomposition of the network, a notion that was heralded in the context of property testing (see HERE (the general case in Section 4)).

Towards the Locality of Vizing's Theorem by Hsin-Hao Su and Hoa T. Vu

A classical theorem of Vizing asserts that $D+1$ colors suffice for coloring the edges of a simple graph of max degree $D+1$, which is the best possible. This work presents two distributed edge-coloring algorithms that run in poly(D,log n) rounds. The first algorithm is randomized and uses only $D+2$ colors, whereas the second one is deterministic and $D+o(log n)$ colors.

Testing Graphs against an Unknown Distribution by Lior Gishboliner and Asaf Shapira

This work refers to the vertex-distribution-free model of testing graph properties (actually, to its dense model variant). It provides a characterization of the class of graph properties that can be tested within query complexity that is independent of the size of the graph (and of the distribution). Unfortunately, this characterization reveals that the class is too sensitive to some definitional choices (specifically, this refers to the necessary condition for having such a `strong tester'). A key issue is whether one is allowed to discard a finite number of graphs when deeming that an algorithm is a tester, and whether this number may depend on the proximity parameter. In particular, it is shown that under the latter definitional choice, every hereditary graph property is strongly testable.

Testing Unateness Nearly Optimally by Xi Chen and Erik Waingarten

This work presents a (one-sided error) tester of unateness (a generalization of monotonicity) for Boolean functions (over $\{0,1\}^n$) having complexity ${\tilde O}(n^{2/3}/\epsilon^2)$, whereas a lower bound of ${\tilde\Omega}(n^{2/3})$ is known. The algorithm makes inherent use of adaptive queries, raising the question of whether such performance can be obtained by a non-adaptive algorithm, but it is known that this cannot be achieved with one-sided error.

Static Data Structure Lower Bounds Imply Rigidity by Zeev Dvir, Alexander Golovnev, and Omri Weinstein

For an m-by-n matrix M, representing $m\gg n$ possible linear queries regarding $n$ input values, a linear data retrieval scheme consists of an s-by-n matrix P of precomputed linear combinations of the inputs and an m-by-s matrix of t-sparse probing-queries Q used to answers the actual queries. Hence $M=QP$, and the goal is to minimize the storage size $s$ and the retrieval time $t$. This paper relates this problem to the non-rigidity of $M$; that is, its representation as $S+R$ such that S is (row) sparse and R has low rank.

This surprising relation is based on a re-interpretation of the two problems as two (`geometric') notions of dimension of the column space of $M$; that is, the maximal dimension of its intersection with any $t$-sparse subspace and the minimal dimension of a $t$-sparse subspace that contains $M$, where a t-sparse subspace is a space spanned by the columns of a $t$-row-sparse matrix.

Solving Linear Programs in the Current Matrix Multiplication Time by Michael Cohen, Yin Tat Lee, and Zhao Song

Algorithmic improvements for solving LPs seem to leg behind the algorithmic improvements for matrix multiplication (MM), at times catching up but currently not. This paper presents a reduction of solving LPs to MM with an additive overhead of $n^{13/6}$. The reduction seems to use two variants of MM, one for square matrices and one for multiplying a square matrix by a rectangular one (i.e., $n$-by-$n^\alpha$ matrix) in time $n^{2+o(1)}$. Currently, the complexity is dominated by the first problem (i.e., the square matrix case).

Sylvester-Gallai type theorems for quadratic polynomials by Amir Shpilka

I am not a member of the worship of the use classical mathematics in TOC, but (as articulated by Amir) this specific progress on a classically flavored math problem arises genuinely from an attempt to make progress on the TOC project of PIT (polynomial identity testing).

Given that this progress reduces to its special case that refers to depth-three arithmetic circuits, one should not look down at a step made on an even more restricted subclass of circuits. Actually, the current work fell short of accommodating this step, but a follow-up work by Amir and Shir Peleg does accomplish it.

Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes by Dylan McKay, Cody Murray, and Ryan Williams

This fantastic work provides a crystal clear and highly appealing illustration of the paradigm of obtaining circuit lower bounds via the design of (better) algorithms. For me, this was the high point of the conference, and attending Dylan's talk compensated me for the hardships of being subjected to FCRC and to the weather. For more comments, see Choice 268.

Link to the corresponding abstracts (and papers)

See STOC'19 program.


Back to list of Oded's choices.