Oded Lachish

According to our database, Oded Lachish authored at least 40 papers between 2001 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

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

Marcel Dall'Agnol, Tom Gur, Oded Lachish

SIAM J. Comput., December, 2023

2022

Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs.

Qing Chen, Oded Lachish, Sven Helmer, Michael H. Böhlen

Proc. VLDB Endow., 2022

When you come at the kings you best not miss.

Oded Lachish, Felix Reidl, Chhaya Trehan

CoRR, 2022

Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended version).

Qing Chen, Oded Lachish, Sven Helmer, Michael H. Böhlen

CoRR, 2022

When You Come at the King You Best Not Miss.

Oded Lachish, Felix Reidl, Chhaya Trehan

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021

On the Power of Relaxed Local Decoding Algorithms.

Tom Gur, Oded Lachish

SIAM J. Comput., 2021

2020

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

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

Electron. Colloquium Comput. Complex., 2020

2019

A Lower Bound for Relaxed Locally Decodable Codes.

Tom Gur, Oded Lachish

Electron. Colloquium Comput. Complex., 2019

Longest paths in 2-edge-connected cubic graphs.

Nikola K. Blanchard, Eldar Fischer, Oded Lachish, Felix Reidl

CoRR, 2019

Improving and Extending the Testing of Distributions for Shape-Restricted Properties.

Eldar Fischer, Oded Lachish, Yadu Vasudev

Algorithmica, 2019

2017

Cellular automata simulation on FPGA for training neural networks with virtual world imagery.

Olivier Van Acker, Oded Lachish, Graeme Burnett

Proceedings of the IEEE Conference on Computational Intelligence and Games, 2017

2016

Testing Read-Once Formula Satisfaction.

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

ACM Trans. Comput. Theory, 2016

Min-Sum 2-Paths Problems.

Trevor I. Fenner, Oded Lachish, Alexandru Popa

Theory Comput. Syst., 2016

Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs.

Oded Lachish, Igor Razgon

CoRR, 2016

2015

Trading query complexity for sample-based testing and multi-testing scalability}.

Eldar Fischer, Oded Lachish, Yadu Vasudev

Electron. Colloquium Comput. Complex., 2015

2014

Partial tests, universal tests and decomposability.

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

Proceedings of the Innovations in Theoretical Computer Science, 2014

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

Oded Lachish

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

The covering and boundedness problems for branching vector addition systems.

Stéphane Demri, Marcin Jurdzinski, Oded Lachish, Ranko Lazic

J. Comput. Syst. Sci., 2013

Some properties are not even partially testable.

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

Electron. Colloquium Comput. Complex., 2013

Analysis of Cluster Structure in Large-Scale English Wikipedia Category Networks.

Thidawan Klaysri, Trevor I. Fenner, Oded Lachish, Mark Levene, Panagiotis Papapetrou

Proceedings of the Advances in Intelligent Data Analysis XII, 2013

2012

On the query complexity of testing orientations for being Eulerian.

Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman, Orly Yahalom

ACM Trans. Algorithms, 2012

Testing Formula Satisfaction.

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

Proceedings of the Algorithm Theory - SWAT 2012, 2012

Improved competitive ratio for the matroid secretary problem.

Sourav Chakraborty, Oded Lachish

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Parity Games on Graphs with Medium Tree-Width.

John Fearnley, Oded Lachish

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010

Two-phase algorithms for the parametric shortest path problem

Eldar Fischer, Oded Lachish, Raphael Yuster

CoRR, 2010

Two-phase Algorithms for the Parametric Shortest Path Problem.

Sourav Chakraborty, Eldar Fischer, Oded Lachish, Raphael Yuster

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009

Spanning connectivity games

Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani

CoRR, 2009

Wiretapping a Hidden Network.

Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani

Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

Hilbert's Thirteenth Problem and Circuit Complexity.

Kristoffer Arnsfelt Hansen, Oded Lachish, Peter Bro Miltersen

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Power Indices in Spanning Connectivity Games.

Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani

Proceedings of the Algorithmic Aspects in Information and Management, 2009

2008

Space Complexity Vs. Query Complexity.

Oded Lachish, Ilan Newman, Asaf Shapira

Comput. Complex., 2008

2007

Lower bounds for testing Euclidean Minimum Spanning Trees.

Oren Ben-Zwi, Oded Lachish, Ilan Newman

Inf. Process. Lett., 2007

Sound 3-query PCPPs are Long.

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

Electron. Colloquium Comput. Complex., 2007

Testing Properties of Constraint-Graphs.

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Electron. Colloquium Comput. Complex., 2007

Testing <i>st</i> -Connectivity.

Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman

Proceedings of the Approximation, 2007

2005

Testing Orientation Properties

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Electron. Colloquium Comput. Complex., 2005

Languages that are Recognized by Simple Counter Automata are not necessarily Testable

Oded Lachish, Ilan Newman

Electron. Colloquium Comput. Complex., 2005

2004

Testing Periodicity

Oded Lachish, Ilan Newman

Electron. Colloquium Comput. Complex., 2004

2002

Hole analysis for functional coverage data.

Oded Lachish, Eitan Marcus, Shmuel Ur, Avi Ziv

Proceedings of the 39th Design Automation Conference, 2002

2001

Explicit lower bound of <i>4.5n - o(n)</i> for boolena circuits.

Oded Lachish, Ran Raz

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001