Oded Lachish

SODA Conference 2021 Conference Paper

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy

• Marcel de Sena Dall'Agnol
• Tom Gur
• Oded Lachish

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes q adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with sample complexity. We also prove that this transformation is nearly optimal, and admits a scheme for constructing privacy-preserving local algorithms. Using the unified view that our structural theorem provides, we obtain the following results. • We strengthen the state-of-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity; this resolves an open problem raised by Gur and Lachish (SODA 2020). • We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity; this resolves a problem left open in a work of Fischer, Lachish, and Vasudev (FOCS 2015) by extending their main result to adaptive testers. • We prove that the known separation between proofs of proximity and testers is essentially maximal; this resolves a problem left open by Gur and Rothblum (ECCC 2013, Computational Complexity 2018) regarding sublinear-time delegation of computation. Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal–Szemerédi theorem.

SODA Conference 2020 Conference Paper

On the Power of Relaxed Local Decoding Algorithms

• Tom Gur
• Oded Lachish

A locally decodable code (LDC) C: {0, 1} k → {0, 1} n is an error correcting code that admits algorithms for recovering individual bits of the message by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to distributed storage. However, despite nearly two decades of extensive study, the best known constructions of LDCs with O (1)-query decoding algorithms have super-polynomial blocklength. The notion of relaxed LDCs is a natural relaxation of LDCs, which aims to bypass the foregoing barrier by requiring local decoding of nearly all individual message bits, yet allowing decoding failure (but not error) on the rest. State of the art constructions of O (1)-query relaxed LDCs achieve blocklength n = O ( k 1+ γ ) for an arbitrarily small constant γ. Using algorithmic and combinatorial techniques, we prove an impossibility result, showing that codes with blocklength n = k 1+o(1) cannot be relaxed decoded with O (1)-query algorithms. This resolves an open problem raised by Goldreich in 2004.

FOCS Conference 2015 Conference Paper

Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability

• Eldar Fischer
• Oded Lachish
• Yadu Vasudev

We show that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Gold Reich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than 1, power of n. Since the query distribution of the sample-based algorithm is not dependent at all on the property, or the original algorithm, this has many implications in scenarios where there are many properties that need to be tested for concurrently, such as testing (relatively large) unions of properties, or converting a Merlin-Arthur Proximity proof (as per [Gur and Rothblum, 2013]) to a proper testing algorithm. The proof method involves preparing the original testing algorithm for a combinatorial analysis. For the analysis we develop a structural lemma for hyper graphs that may be of independent interest. When analyzing a hyper graph that was extracted from a 2-sided test, it allows for finding generalized sunflowers that provide for a large-deviation type analysis. For 1-sided tests the bounds can be improved further by applying Janson's inequality directly over our structures.

FOCS Conference 2014 Conference Paper

O(log log Rank) Competitive Ratio for the Matroid Secretary Problem

• Oded Lachish

In the Matroid Secretary Problem (MSP), the elements of the ground set of a Matroid are revealed on-line one by one, each together with its value. An algorithm for the MSP is called Matroid-Unknown if, at every stage of its execution, it only knows (i) the elements that have been revealed so far and their values and (ii) an oracle for testing whether or not a subset the elements that have been revealed so far forms an independent set. An algorithm is called Known-Cardinality if it knows (i), (ii) and also knows from the start the cardinality n of the ground set of the Matroid. We present here a Known-Cardinality algorithm with a competitive-ratio of order log log the rank of the Matroid. The prior known results for a OC algorithm are a competitive-ratio of log the rank of the Matroid, by Babaioff et al. (2007), and a competitive-ratio of square root of log the rank of the Matroid, by Chakraborty and Lachish (2012).

SODA Conference 2012 Conference Paper

Improved competitive ratio for the matroid secretary problem

• Sourav Chakraborty 0001
• Oded Lachish

MFCS Conference 2011 Conference Paper

Parity Games on Graphs with Medium Tree-Width

• John Fearnley
• Oded Lachish

Abstract This paper studies the problem of solving parity games on graphs with bounded tree-width. Previous work by Obdržálek has produced an algorithm that uses \(n^{O(k^2)}\) time and \(n^{O(k^2)}\) space, where k is the tree-width of the graph that the game is played on. This paper presents an algorithm that uses n O ( k log n ) time and O ( n + k log n ) space. This is the fastest known algorithm for parity games whose tree-width k satisfies (in standard asymptotic notation) k ∈ ω (log n ) and \(k \in o(\sqrt{n}/\log n)\).

STOC Conference 2001 Conference Paper

Explicit lower bound of 4. 5n - o(n) for boolena circuits

• Oded Lachish
• Ran Raz

We prove a lower bound of 4.5n - o(n) for the circuit complexity of an explicit Boolean function (that is, a function constructible in deterministic polynomial time), over the basis U_2 . That is, we obtain a lower bound of 4.5n - o(n) for the number of {and,or} gates needed to compute a certain Boolean function, over the basis {and,or,not} (where the not gates are not counted). Our proof is based on a new combinatorial property of Boolean functions, called Strongly-Two-Dependence , a notion that may be interesting in its own right. Our lower bound applies to any Strongly-Two-Dependent Boolean function.