Skip to main content

Dr Oded Lachish

Positions held:
  • Reader in Computer Science, School of Computing and Mathematical Sciences
Email
  • Supervision and teaching

    Supervision and teaching

    Supervision

    Supervisions within Birkbeck:
    3

    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)
    • 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