Conference Papers by Oded Lachish


Improving and extending the testing of distributions for shape-restricted properties.
    With: Eldar Fischer and Yadu Vasudev.
    Accepted to: Symposium on Theoretical Aspects of Computer Science (STACS'17) 
Fast Computation of Continental-Sized Isochrones.
    With: Paolo Bolzoni and Sven Helmer.
    9th Int. Conf. on Geographic Information Science (GIScience'16).     
Trading query complexity for sample-based testing and multi-testing scalability.
    With: Eldar Fischer and Yadu Vasudev.
    Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS'15).
    Pages: 1163 - 1182 
O(log log rank) Competitive-Ratio for the Matroid Secretary Problem (the Known Cardinality Variant).
    Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS'14).
    Pages: 326 - 335
Partial Tests, Universal Tests and Decomposability.
    With: Eldar Fischer and Yonatan Goldhirsh.
    Proceedings of the 5th Innovations in Theoretical Computer Science Conference (ITCS'14). 
    Pages: 483 - 500
Min-Sum 2-Paths Problems.
    With: Alexandru Popa and Trevor Fenner.
    Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA'13). 
    Pages: 1 - 11
Analysis of Cluster Structure in Large-Scale English Wikipedia Category Networks.
    With: Trevor Fenner, Thidawan Klaysri, Mark Levene and Panagiotis Papapetrou.
    Proceedings of the International Symposium on Intelligent Data Analysis (IDA'13). 
    Pages: 261 - 272
Testing Formula Satisfaction.
    With: Eldar Fischer and Yonatan Goldhirsh.
    13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'12). 
    Pages: 376 - 387
Improved Competitive Ratio for the Matroid Secretary Problem.
    With: Sourav Chakraborty.
    ACM-SIAM Symposium on Discrete Algorithms (SODA'12). 
    Pages: 1702 - 1712
Parity Games on Graphs with Medium Tree-width.
    With: John Fearnley.
    36th International Symposium on Mathematical Foundations of Computer Science (MFCS'11).
    Pages: 303 - 314
Two-Phase Algorithms for the Parametric Shortest Path Problem.
    With: Sourav Chakraborty, Eldar Fischer and Raphy Yuster.
    Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS'10).
    Pages: 167 - 178
The Covering and Boundedness Problems for Branching Vector Addition Systems.
    With: Stephane Demri, Marcin Jurdzinski and Ranko Lazic.
    Proceedings of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS'09).
    Pages: 181 - 192
Wiretapping a Hidden Network.
    With: Haris Aziz, Mike Paterson and Rahul Savani.
    Proceedings of the fifth workshop on internet & network economics (WINE'09).
    Pages: 438 - 446
Hilbert's Thirteenth Problem and Circuit Complexity.
    With: Kristoffer Arnsfelt Hansen and Peter Bro Miltersen.
    Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC'09).
    Pages: 153 - 162
Power Indices in Spanning Connectivity Games.
    With: Haris Aziz, Mike Paterson and Rahul Savani.
    Proceedings of Algorithmic Aspects in Information and Management (AAIM'09).
    Pages: 55 - 67
On the Query Complexity of Testing Orientations for Being Eulerian.
    With: Eldar Fischer, Arie Matsliah, Ilan Newman and Orly Yahalom.
    Proceedings of the 12th RANDOM (and the 11th APPROX) (2008).
    Pages: 402 - 415
Sound 3-query PCPPs are Long.
    With: Eli Ben Sasson, Prahladh Harsha and Arie Matsliah.
    Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08).
    Pages: 686-697
Testing s-t Connectivity.
    With: Sourav Chakraborty, Eldar Fischer, Arie Matsliah and Ilan Newman.
    Proceedings of the 11th RANDOM (and the 10th APPROX) (2007).
    Pages: 366 - 377
Testing Properties of Constraint-Graphs.
    With: Shirley Ginzburg Halevy, Ilan Newman and Dekel Tsur.
    Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC'07).
    Pages: 264 - 277
Space Complexity vs. Query Complexity.
    With: Ilan Newman and Asaf Shapira.
    Proceedings of the 10th RANDOM (and the 9th APPROX) (2006).
    Pages: 426 - 437
Testing Periodicity.
    With: Ilan Newman.
    Proceedings of the 9th RANDOM (and the 8th APPROX) (2005).
    Pages: 366 - 377
Explicit Lower Bound of 4.5n - o(n) for Boolean Circuits.
    With: Ran Raz.
    Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC'01).
    Pages: 399-408
Hole Analysis for Functional Coverage Data.
    With: Eitan Marcus, Shmuel Ur and Avi Ziv.
    Proceedings of the 39th Design Automation Conference (DAC'02).
    Pages: 807-812
Object-Oriented High Level Modelling of InfiniBand to PCI-X Bridge.
    With: Avi Ziv.
    Proceedings of the Forum on Specification and Design Languages (Best of FDL'02).
    Pages: 243-253

Journal Papers by Oded Lachish


Testing Read-Once Formula Satisfaction.
    With: Eldar Fischer and Yonatan Goldhirsh.
    The ACM Transactions on Computation Theory (TOCT) 8(2): 5 (2016). 
Min-Sum 2-Paths Problems.
    With: Alexandru Popa and Trevor Fenner.
    Theory of Computing Systems (TCS), 58(1), 94-110 (2016). 
The Covering and Boundedness Problems for Branching Vector Addition Systems.
    With: Stephane Demri, Marcin Jurdzinski and Ranko Lazic.
    Journal of Computer and System Sciences (JCSS) 79(1): 23-38 (2013).
On the Query Complexity of Testing Orientations for Being Eulerian.
    With: Eldar Fischer, Arie Matsliah, Ilan Newman and Orly Yahalom.
    ACM Transactions on Algorithms 8(2): 1-41 (2012).
Testing Periodicity.
    With: Ilan Newman.
    Algorithmica 60(2): 401 - 420 (2011).
Sound 3-query PCPPs are Long.
    With: Eli Ben Sasson, Prahladh Harsha and Arie Matsliah.
    The ACM Transactions on Computation Theory 1(2): 1-49 (2009).
Space Complexity vs. Query Complexity.
    With: Ilan Newman and Asaf Shapira.
    Computational Complexity RANDOM'06 Special Issue 17(1): 70-93 (2008).
Lower Bounds for Testing Euclidean Minimum Spanning Trees.
    With: Oren Ben-Zwi and Ilan Newman.
    Information Processing Letters 102(6): 219-225 (2007).

Patents by Oded Lachish

Convolutional interleaving/de-interleaving method using pointer incrementing across predetermined distances and apparatus for data transmission.
     With: Ron Eliyahu and Marc Neustadter.
     United States Patent 6014761