Dr Oded Lachish

Overview
Overview
Biography
 PostDoc at the Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick , Coventry, United Kingdom, 20072010.
 PostDoc at the Department of Computer Science, Technion, Haifa, Israel. My host was Eli Ben Sasson, 20062007.
Office hours
Tuesday 5pm to 6pm
If you intend to visit my office during reception hours, kindly send me an email at least a day prior.
Qualifications
 PhD in Computer Science, Haifa University, 2007
 MSc Computer Science, Weizmann Institute of Science, 2001
 BSc Physics and Mathematics, Hebrew University, 1995
Web profiles
Administrative responsibilities
 Post Graduate Research Lead
 MPhil Admissions Tutor
 Post Graduate Research Program Director
 Algorithm's group lead
 MRes Admissions Tutor

Research
Research
Research interests
 Combinatorial Algorithms
 Computational Complexity
Research overview
My area of research is Computer Science with a focus on Theory, Design and Application of Algorithms and Computational Complexity. More specifically:
Algorithms – pushing algorithms to the limit: design of highly efficient theoretical algorithms that
return meaningful results after reading only a very small portion of the input,  design of algorithms for implementation, with a focus on graph algorithms,
 optimisation of software implementation of
algorithms, and  evaluation of implemented algorithms.
Computational Complexity – my focus is on goals such as lower bounds for Locally Decodable Codes, Circuits, and the Matroid Secretary Problem (my latest conjecture for the problem). The goals in this line of research are long term due to the nature of the area.Research Centres and Institutes
Research clusters and groups
 Lead, Algorithms

Supervision and teaching
Supervision and teaching
Supervision
I welcome enquiries from prospective PhD students who are interested in undertaking research in any of my areas of research interest, especially if you aspire to write software that runs surprisingly fast.
Current doctoral researchers

CHRISTINE AWOFESO

PATRICK GREAVES

ANGELINA MCDONALD
Teaching
Teaching modules
 Mathematics for Computing (COIY040H4)
 Mathematics for Computing (COIY040H4)
 Research Methods (COIY055H7)
 Research Methods (COIY055H7)


Publications
Publications
Article
 Dall'Agnol, M. and Gur, T. and Lachish, Oded (2023) A structural theorem for local algorithms with applications to coding, testing, and privacy. SIAM Journal on Computing 52 (6), pp. 14131463. ISSN 00975397.
 Lachish, Oded and Reidl, Felix and Trehan, Chhaya (2022) When you come at the King you best not miss. Leibniz International Proceedings in Informatics (LIPIcs). 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) 250, pp. 25:125:12. ISSN 18688969.
 Lachish, Oded and Gur, T. (2021) On the power of relaxed Local Decoding Algorithms. SIAM Journal on Computing 50 (2), pp. 788813. ISSN 00975397.
 Lachish, Oded and Fischer, E. and Vasudev, Y. (2019) Improving and extending the testing of distributions for shaperestricted properties. Algorithmica 81 (9), pp. 37653802. ISSN 01784617.
 Fenner, Trevor and Lachish, Oded and Popa, A. (2016) Minsum 2paths problems. Theory of Computing Systems 58 (1), pp. 94110. ISSN 14324350.
 Fischer, E. and Lachish, Oded and Vasudev, Y. (2015) Trading query complexity for samplebased testing and multitesting scalability. Symposium on Foundations of Computer Science pp. 11631182. ISSN 02725428.
 Demri, S. and Jurdziński, M. and Lachish, Oded and Lazić, R. (2013) The covering and boundedness problems for branching vector addition systems. Journal of Computer and System Sciences 79 (1), pp. 2338. ISSN 00220000.
 Fischer, E. and Lachish, Oded and Matsliah, A. and Newman, I. and Yahalom, O. (2012) On the query complexity of testing orientations for being Eulerian. ACM Transactions on Algorithms 8 (2), pp. 141. ISSN 15496325.
 Lachish, Oded and Newman, I. (2011) Testing periodicity. Algorithmica 60 (2), pp. 401420. ISSN 01784617.
 BenSasson, E. and Harsha, P. and Lachish, Oded and Matsliah, A. (2009) Sound 3query PCPPs are long. ACM Transactions on Computation Theory 1 (2), pp. 149. ISSN 19423454.
 Lachish, Oded and Newman, I. and Shapira, A. (2008) Space complexity Vs. query complexity. Computational Complexity 17 (1), pp. 7093. ISSN 10163328.
Book Section
 Fisher, E. and Lachish, Oded and Vasudev, Y. (2017) Improving and extending the testing of distributions for shaperestricted properties. In: Vollmer, H. and Vallée, B. (eds.) 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics. Leibniz International. pp. 31:131:14. ISBN 9783959770286.
 Fischer, E. and Goldhirsh, Y. and Lachish, Oded (2014) Partial tests, universal tests and decomposability. In: ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer science. New York, U.S.: ACM. pp. 483500. ISBN 9781450326988.
 Lachish, Oded (2014) O(log log Rank) competitive ratio for the Matroid Secretary Problem. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) (2014). Piscataway, U.S.: IEEE. pp. 326225. ISBN 9781479965175.
 Chakraborty, S. and Lachish, Oded (2012) Improved competitive ratio for the matroid secretary problem. In: SODA 2012: Proceedings of the TwentyThird Annual ACMSIAM Symposium on Discrete Algorithms. SIAM. pp. 17021712.
 Fischer, E. and Goldhirsh, Y. and Lachish, Oded (2012) Testing formula satisfaction. In: Fomin, F.V. and Kaski, P. (eds.) Algorithm Theory – SWAT 2012. Lecture Notes in Computer Science. Berlin, Germany: Springer. pp. 376387. ISBN 9783642311550.
 Fearnley, J. and Lachish, Oded (2011) Parity games on graphs with medium treewidth. In: Murlak, F. and Sankowski, P. (eds.) Mathematical Foundations of Computer Science. Lecture Notes in Computer Science. Berlin, Germany: Springer Verlag. pp. 303314. ISSN 03029743. ISBN 9783642229930.
 Chakraborty, S. and Fischer, E. and Lachish, Oded and Yuster, R. (2010) Twophase algorithms for the parametric shortest path problem. In: JeanYves, M. and Schwentick, T. (eds.) 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics. Dagstuhl, Germany: Schloss Dagstuhl. pp. 168176. ISBN 9783939897163.
 Aziz, H. and Lachish, Oded and Paterson, M. and Savani, R. (2009) Power indices in spanning connectivity games. In: Goldberg, A. and Zhou, Y. (eds.) Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science. Berlin, Germany: Springer Verlag. pp. 5567. ISSN 03029743. ISBN 9783642021572.
 Aziz, H. and Lachish, Oded and Paterson, M. and Savani, R. (2009) Wiretapping a hidden network. In: Leonardi, S. (ed.) Internet and Network Economics. Lecture Notes in Computer Science. Berlin, Germany: Springer Verlag. pp. 438446. ISSN 03029743. ISBN 9783642108419.
 Demri, S. and Jurdziński, M. and Lachish, Oded and Lazić, R. (2009) The covering and boundedness problems for branching vector addition systems. In: Kannan, R. and Kumar, K.N. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics. Dagstuhl, Germany: Schloss Dagstuhl. pp. 181192. ISBN 9783939897132.
 Hansen, K.A. and Lachish, Oded and Miltersen, P.B. (2009) Hilbert’s thirteenth problem and circuit complexity. In: Dong, Y.F. and Du, D.Z. and Ibarra, O.H. (eds.) Algorithms and Computation. Lecture Notes in Computer Science. Berlin, Germany: Springer Verlag. pp. 153162. ISSN 03029743. ISBN 9783642106316.
 BenSasson, E. and Harsha, P. and Lachish, Oded and Matsliah, A. (2008) Sound 3query PCPPs are long. In: Aceto, L. and Damgård, I. and Goldberg, L.A. and Halldórsson, M.M. and Ingólfsdóttir, A. and Walukiewicz, I. (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science. Berlin, Germany: Springer Verlag. pp. 686697. ISSN 03029743. ISBN 9783540705758.
 Fischer, E. and Lachish, Oded and Newman, I. and Matsliah, A. and Yahalom, O. (2008) On the query complexity of testing orientations for being Eulerian. In: Goel, A. and Jansen, K. and Rolim, J. and Rubinfeld, J. (eds.) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Berlin, Germany: Springer Verlag. pp. 402415. ISSN 03029743. ISBN 9783540853633.
 Halevy, S. and Lachish, Oded and Newman, I. and Tsur, D. (2007) Testing properties of constraintgraphs. In: TwentySecond Annual IEEE Conference on Computational Complexity (CCC'07). IEEE Computer Society. ISBN 9780769527809.
 Lachish, Oded and Newman, I. (2005) Testing periodicity. In: Chekuri, C. and Jansen, K. and Rolim, J.D.P. and Trevisan, L. (eds.) Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques. Lecture Notes in Computer Science. Springer. pp. 366377. ISBN 9783540282396.
 Lachish, Oded and Raz, R. (2001) Explicit lower bound of 4.5n  o(n) for boolena circuits. In: Vitter, J.S. and Spirakis, P. and Yannakakis, M. (eds.) STOC '01: Proceedings of the thirtythird annual ACM symposium on Theory of computing. Association for Computing Machinery. pp. 399408. ISBN 9781581133493.
Conference Item
 Chen, Qing and Helmer, Sven and Lachish, Oded and Bohlen, Michael (2022) Dynamic Spanning Trees for connectivity queries on fullydynamic undirected graphs. 48th International Conference on Very Large Databases, 2022, Sydney, Australia
 Dall'Agnol, M. and Gur, T. and Lachish, Oded (2020) A structural theorem for local algorithms with applications to coding, testing, and privacy. ACMSIAM Symposium on Discrete Algorithms (SODA21), 2020, Online
 Lachish, Oded and Gur, Tom (2019) A Lower Bound for Relaxed Locally Decodable Codes. ACMSIAM Symposium on Discrete Algorithms (SODA20), 2019, Salt Lake City, U.S.
External Repositories