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.