Skip to main content

Dr Oded Lachish

Positions held:
  • Reader in Computer Science, School of Computing and Mathematical Sciences
Address

Room 166, Malet Street

Email
  • Overview

    Overview

    Biography

    • Post-Doc at the Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick , Coventry, United Kingdom, 2007-2010.
    • Post-Doc at the Department of Computer Science, Technion, Haifa, Israel. My host was Eli Ben Sasson, 2006-2007.

    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

    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:

    1. design of highly efficient theoretical algorithms that
      return meaningful results after reading only a very small portion of the input,
    2. design of algorithms for implementation, with a focus on graph algorithms, 
    3. optimisation of software implementation of
      algorithms, and 
    4. 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

  • Supervision and teaching

    Supervision and teaching

    Supervision

    Supervisions within Birkbeck:
    3

    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
      Nature of supervision:
      Joint Principal Supervisor, onwards
    • PATRICK GREAVES
      Nature of supervision:
      Joint Principal Supervisor, onwards
    • ANGELINA MCDONALD
      Nature of supervision:
      Joint Principal Supervisor, onwards
      Title of thesis:
      Graph Algorithms and Parameterized Complexity
      Description:

      This research is about producing highly efficient algorithms taken from graph theory, and extending their use towards practical application in network science. With new approaches to algorithm design, I hope to push the boundary of what is computationally-feasible at present by delivering data analysis on certain types of large graphs in shorter response times.

    Teaching

    Teaching modules

    • Mathematics for Computing (COIY040H4)
    • Mathematics for Computing (COIY040H4)
    • Research Methods (COIY055H7)
    • Research Methods (COIY055H7)
  • Publications

    Publications

    Article

    Book Section

    • Fisher, E. and Lachish, Oded and Vasudev, Y. (2017) Improving and extending the testing of distributions for shape-restricted 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:1-31: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. 483-500. 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. 326-225. ISBN 9781479965175.
    • Chakraborty, S. and Lachish, Oded (2012) Improved competitive ratio for the matroid secretary problem. In: SODA 2012: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. pp. 1702-1712.
    • 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. 376-387. ISBN 9783642311550.
    • Fearnley, J. and Lachish, Oded (2011) Parity games on graphs with medium tree-width. In: Murlak, F. and Sankowski, P. (eds.) Mathematical Foundations of Computer Science. Lecture Notes in Computer Science. Berlin, Germany: Springer Verlag. pp. 303-314. ISSN 0302-9743. ISBN 9783642229930.
    • Chakraborty, S. and Fischer, E. and Lachish, Oded and Yuster, R. (2010) Two-phase algorithms for the parametric shortest path problem. In: Jean-Yves, M. and Schwentick, T. (eds.) 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics. Dagstuhl, Germany: Schloss Dagstuhl. pp. 168-176. 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. 55-67. ISSN 0302-9743. 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. 438-446. ISSN 0302-9743. 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. 181-192. 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. 153-162. ISSN 0302-9743. ISBN 9783642106316.
    • Ben-Sasson, E. and Harsha, P. and Lachish, Oded and Matsliah, A. (2008) Sound 3-query 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. 686-697. ISSN 0302-9743. 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. 402-415. ISSN 0302-9743. ISBN 9783540853633.
    • Halevy, S. and Lachish, Oded and Newman, I. and Tsur, D. (2007) Testing properties of constraint-graphs. In: Twenty-Second 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. 366-377. 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 thirty-third annual ACM symposium on Theory of computing. Association for Computing Machinery. pp. 399-408. ISBN 9781581133493.

    Conference Item

    External Repositories