A few works from FOCS'14

The following three works were presented in FOCS'14, and can be obtained from the program's website. Additional works presented at FOCS'14 have appeared as prior choices.

Preventing False Discovery in Interactive Data Analysis is Hard (by Moritz Hardt and Jonathan Ullman)

Iterative data analysis is modeled as an adaptive sequence of statistical queries (a la the model of Kearns), which are answered by a single sample of the data (rather than by the data's statistic itself). The issue is that the error in an adaptive sequence of queries may be much larger than the error in a nonadaptive sequence of queries, because the adaptive queries may depend on the sample through the information on the sample provided by the answers to prior queries. That is, answers to statistical queries that are based on the sample may reveal information on the sample rather than on the universe. The amount of such extra information is related to the non-privacy of the mechanism used to answer these queries, and hence bounds on privacy of certain mechanisms become relevant.

The main result is that the existence of one-way functions imply that any computationally efficient mechanism of answering adaptive queries will fail for $n^3.01$ queries (recently improved to $n^2.01$). In contrast, such mechanisms can handle $n^2$ queries, whereas non-efficient mechanisms can handle exponentially many queries.

New algorithms and lower bounds for monotonicity testing (by Xi Chen, Rocco Servedio, and Li-Yang Tan)

The issue is the query complexity of non-adaptive testers for monotonicity of Boolean functions. The main result in this paper is a lower bound of the form $n^Omega(1)$, recently improved to $n^0.499$. They also improve the upper bound from $\poly(1/\eps)\tildeO(n^{7/8})$ to $\poly(1/\eps)\tildeO(n^{5/6})$.

Path-Finding Methods for Linear Programming: Solving Linear Programs in tildeO(sqrt(rank)) Iterations and Faster Algorithms for Maximum Flow (by Yin Tat Lee and Aaron Sidford)

The new algorithm is based on an iterative process that updates auxiliary information that is useful for the next step along with making the current step. That is, in each iteration, the algorithm moves to a better internal point based on weights that determine a good direction in which to move, whereas these weights are found based on the point reached in the prior iteration. At a very high level this strategy reminds me of the strategy employed in the polynomial-time approximation of the permanent of non-negative matrices (by Jerrum, Sinclair, and Vigoda, 33rd STOC, 2001) as abstracted in my review.

Back to list of Oded's choices.