Conference Papers by Oded Lachish


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

    With: Olivier Van Acker and Graeme Burnett.
    Conference on Computational Intelligence in games (CIG'17) 
    Pages: 304 - 305 

Improving and extending the testing of distributions for shape-restricted properties.

    With: Eldar Fischer and Yadu Vasudev.
    Symposium on Theoretical Aspects of Computer Science (STACS'17) 
    Pages: 1 - 14 

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