On a few works presented at ITCS'19

I enjoyed very much the format of the program of ITCS19: In my opinion, the brief 1-minute summaries provided by the session chairs were extremely useful towards preparing intellectually for the presentation themselves; the 12-minute slot per presentation seems to works very well in helping the speakers focus on the main messages of the work rather than on details of the proofs. Unfortunately, I only took very laconic notes from the sessions that I attended, and not from all presentations in these sessions.


Spanoids - an abstraction of spanning structures, and a barrier for LCCs by Zeev Dvir, Sivakanth Gopi, Yuzhou Gu and Avi Wigderson
This work presents and abstraction of the known lower bounds for Locally Decodable/Correctable Codes, and a demonstration that within this abstract model the known lower bounds are the best possible.

Algorithmic Polarization for Hidden Markov Models by Venkatesan Guruswami, Preetum Nakkiran and Madhu Sudan.
Polar codes are rigorously analyzed assuming random noise in which the noise is a sequence of IIDs. Aiming at treating more general models of random noise, this work reduces the analysis of noise generated by a hidden Markov chain to the known analysis of the IID case.

Erasures vs. Errors in Local Decoding and Property Testing by Sofya Raskhodnikova, Noga Ron-Zewi and Nithin Varma.
This work present a separation between the complexity of tolerant testing and the complexity of testing in the presence of erasures (i.e., erasure-resilient property testing), a model introduced in a prior work of Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma.

On Solving Linear Systems in Sublinear Time by Alexandr Andoni, Robert Krauthgamer and Yosef Pogrow.
This work demonstrates the applicability of the notion of local computation algorithms (LCAs) to the domain of linear algebra. In particular, it shows that certain types of linear systems can be solved by a LCA in polylogarithmic time (per query to a coordinate of the output).

Adaptive Boolean Monotonicity Testing in Total Influence Time by Deeparnab Chakrabarty and C. Seshadhri.
The point of this work is relating the complexity of property testing to a natural parameter of the tested object (i.e., the influence of the tested function) rather than to its size parameter (and proximity parameter only).

Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs by Amit Levi and Erik Waingarten.
See comments on choice Nr 250.

A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling by Sepehr Assadi, Michael Kapralov and Sanjeev Khanna.
This work generalizes prior works, showing that the complexity of approximately counting the number of fixed subgraphs in an input graph can be characterized in terms of the fractional edge cover of the subgraph. The result holds in a model that assumes that edges in the input can be sampled in unit time, and raises a natural conjecture that would allow to prove the characterization also in the standard model.

Testing local properties of arrays by Omri Ben-Eliezer.
The work presents a framework that generalizes natural property testing problems regarding functions defined over hypergrids (e.g., monotonicity, convexity, and Lipschitz continuity), but the results are most appealing for one-dimensional arrays.

Local Computation Algorithms for Spanners by Merav Parter, Ronitt Rubinfeld, Ali Vakilian and Anak Yodpinyanee.
This work focuses on presenting sublinear LCAs for finding 3-spanners and 5-spanners, while using a strong form of adjacency queries (in addition to neighbor queries). The answer to such a query indicates not only if the edge exists or not, but rather also its index of the edge at each of its endpoints.

Cubic Formula Size Lower Bounds Based on Compositions with Majority by Anna Gal, Avishay Tal and Adrian Trejo Nunez.
This work derives new lower bounds on formula size by employing "tweaked" random restrictions, where the point is that hitting an $m$-way majority with a random restriction that leaves $o(sqrt(m))$ variables alive trivializes the function. In contrast, we can iteratively hit it with random restrictions that keep two-third power of the number of surviving variables alive, and set some variables so that each remaining variable is influential (i.e., the tweak balances the number of different settings). Indeed, such a tweaked-random process behaves very differently that a random restriction, but its simplification effect on the formula is preserved.

The Orthogonal Vectors Conjecture for Branching Programs and Formulas Daniel Kane and Ryan Williams.
This work shows that in some models of computation (e.g., branching programs and formulas) the straightforward upper bound on the complexity of the orthogonal vectors problem can be (almost) matched by corresponding lower bounds.


Back to list of Oded's choices.