Oded Lachish

Publication Activity (10 Years)

Years Active: 2001-2023
Publications (10 Years): 24

Top Topics

Competitive Ratio

Cellular Automata

Locally Decodable Codes

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Marcel Dall'Agnol, Tom Gur, Oded Lachish
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification. SIAM J. Comput. 52 (6) (2023)
Oded Lachish, Felix Reidl, Chhaya Trehan
When you come at the kings you best not miss. CoRR (2022)
Oded Lachish, Felix Reidl, Chhaya Trehan
When You Come at the King You Best Not Miss. FSTTCS (2022)
Qing Chen, Oded Lachish, Sven Helmer, Michael H. Böhlen
Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs. Proc. VLDB Endow. 15 (11) (2022)
Qing Chen, Oded Lachish, Sven Helmer, Michael H. Böhlen
Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended version). CoRR (2022)
Tom Gur, Oded Lachish
On the Power of Relaxed Local Decoding Algorithms. SIAM J. Comput. 50 (2) (2021)
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy. SODA (2021)
Tom Gur, Oded Lachish
On the Power of Relaxed Local Decoding Algorithms. SODA (2020)
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy. CoRR (2020)
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy. Electron. Colloquium Comput. Complex. 27 (2020)
Tom Gur, Oded Lachish
A Lower Bound for Relaxed Locally Decodable Codes. CoRR (2019)
Eldar Fischer, Oded Lachish, Yadu Vasudev
Improving and Extending the Testing of Distributions for Shape-Restricted Properties. Algorithmica 81 (9) (2019)
Nikola K. Blanchard, Eldar Fischer, Oded Lachish, Felix Reidl
Longest paths in 2-edge-connected cubic graphs. CoRR (2019)
Tom Gur, Oded Lachish
A Lower Bound for Relaxed Locally Decodable Codes. Electron. Colloquium Comput. Complex. 26 (2019)
Olivier Van Acker, Oded Lachish, Graeme Burnett
Cellular automata simulation on FPGA for training neural networks with virtual world imagery. CIG (2017)
Eldar Fischer, Oded Lachish, Yadu Vasudev
Improving and Extending the Testing of Distributions for Shape-Restricted Properties. STACS (2017)
Olivier Van Acker, Oded Lachish, Graeme Burnett
Cellular Automata Simulation on FPGA for Training Neural Networks with Virtual World Imagery. CoRR (2017)
Eldar Fischer, Oded Lachish, Yadu Vasudev
Improving and extending the testing of distributions for shape-restricted properties. CoRR (2016)
Trevor I. Fenner, Oded Lachish, Alexandru Popa
Min-Sum 2-Paths Problems. Theory Comput. Syst. 58 (1) (2016)
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish
Testing Read-Once Formula Satisfaction. ACM Trans. Comput. Theory 8 (2) (2016)
Oded Lachish, Igor Razgon
Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs. CoRR (2016)
Eldar Fischer, Oded Lachish, Yadu Vasudev
Trading query complexity for sample-based testing and multi-testing scalability}. Electron. Colloquium Comput. Complex. 22 (2015)
Eldar Fischer, Oded Lachish, Yadu Vasudev
Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability. FOCS (2015)
Eldar Fischer, Oded Lachish, Yadu Vasudev
Trading query complexity for sample-based testing and multi-testing scalability. CoRR (2015)
Oded Lachish
O(log log rank) Competitive-Ratio for the Matroid Secretary Problem. CoRR (2014)
Oded Lachish
O(log log Rank) Competitive Ratio for the Matroid Secretary Problem. FOCS (2014)
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish
Partial tests, universal tests and decomposability. ITCS (2014)
Trevor I. Fenner, Oded Lachish, Alexandru Popa
Min-Sum 2-Paths Problems. WAOA (2013)
Thidawan Klaysri, Trevor I. Fenner, Oded Lachish, Mark Levene, Panagiotis Papapetrou
Analysis of Cluster Structure in Large-Scale English Wikipedia Category Networks. IDA (2013)
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish
Some properties are not even partially testable. CoRR (2013)
Stéphane Demri, Marcin Jurdzinski, Oded Lachish, Ranko Lazic
The covering and boundedness problems for branching vector addition systems. J. Comput. Syst. Sci. 79 (1) (2013)
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish
Some properties are not even partially testable. Electron. Colloquium Comput. Complex. 20 (2013)
Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman, Orly Yahalom
On the query complexity of testing orientations for being Eulerian. ACM Trans. Algorithms 8 (2) (2012)
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish
Testing Formula Satisfaction. SWAT (2012)
Sourav Chakraborty, Oded Lachish
Improved competitive ratio for the matroid secretary problem. SODA (2012)
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish
Testing Formula Satisfaction CoRR (2012)
John Fearnley, Oded Lachish
Parity Games on Graphs with Medium Tree-Width. MFCS (2011)
Oded Lachish, Ilan Newman
Testing Periodicity. Algorithmica 60 (2) (2011)
Eldar Fischer, Oded Lachish, Raphael Yuster
Two-phase algorithms for the parametric shortest path problem CoRR (2010)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Raphael Yuster
Two-phase Algorithms for the Parametric Shortest Path Problem. STACS (2010)
Kristoffer Arnsfelt Hansen, Oded Lachish, Peter Bro Miltersen
Hilbert's Thirteenth Problem and Circuit Complexity. ISAAC (2009)
Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
Power Indices in Spanning Connectivity Games. AAIM (2009)
Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah
Sound 3-Query PCPPs Are Long. ACM Trans. Comput. Theory 1 (2) (2009)
Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
Wiretapping a hidden network CoRR (2009)
Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
Wiretapping a Hidden Network. WINE (2009)
Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
Spanning connectivity games CoRR (2009)
Stéphane Demri, Marcin Jurdzinski, Oded Lachish, Ranko Lazic
The Covering and Boundedness Problems for Branching Vector Addition Systems. FSTTCS (2009)
Oded Lachish, Ilan Newman, Asaf Shapira
Space Complexity Vs. Query Complexity. Comput. Complex. 17 (1) (2008)
Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah
Sound 3-Query PCPPs Are Long. ICALP (1) (2008)
Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom
On the Query Complexity of Testing Orientations for Being Eulerian. APPROX-RANDOM (2008)
Oren Ben-Zwi, Oded Lachish, Ilan Newman
Lower bounds for testing Euclidean Minimum Spanning Trees. Inf. Process. Lett. 102 (6) (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
-Connectivity. APPROX-RANDOM (2007)
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
Testing Properties of Constraint-Graphs. Electron. Colloquium Comput. Complex. 14 (054) (2007)
Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish
Sound 3-query PCPPs are Long. Electron. Colloquium Comput. Complex. 14 (127) (2007)
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
Testing Properties of Constraint-Graphs. Computational Complexity Conference (2007)
Oded Lachish, Ilan Newman, Asaf Shapira
Space Complexity vs. Query Complexity. Electron. Colloquium Comput. Complex. 13 (103) (2006)
Oded Lachish, Ilan Newman, Asaf Shapira
Space Complexity vs. Query Complexity. APPROX-RANDOM (2006)
Oded Lachish, Ilan Newman
Testing Periodicity. APPROX-RANDOM (2005)
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
Testing Orientation Properties Electron. Colloquium Comput. Complex. (153) (2005)
Oded Lachish, Ilan Newman
Languages that are Recognized by Simple Counter Automata are not necessarily Testable Electron. Colloquium Comput. Complex. (152) (2005)
Oded Lachish, Ilan Newman
Testing Periodicity Electron. Colloquium Comput. Complex. (092) (2004)
Oded Lachish, Eitan Marcus, Shmuel Ur, Avi Ziv
Hole analysis for functional coverage data. DAC (2002)
Oded Lachish, Ran Raz
for boolena circuits. STOC (2001)