This is my old homepage. My new one is here.





Oded Schwartz

I am a Ph.D student at the School of Computer Science at Tel-Aviv University, Israel,
under the supervision of
Prof. Muli Safra and Dr. Amnon Ta-Shma.

Fields of Interest: Theoretical Computer Science, Computational Complexity, Combinatorial Optimization Problems.

Contact Info:

Email: odedsc@tau.ac.il
School of Computer Science
Tel-Aviv University
Tel-Aviv 69978
Israel
Office: (+972)-3-640-5398
Fax:    (+972)-3-640-9357

Curriculum Vitae (ps, pdf)


Publications: 

  • On Parallel-Repetition, Unique-Game and Max-Cut (ps, pdf,bibtex)
    Muli Safra and Oded Schwartz.
    Submitted, 2007.

  • An Elementary Construction of Constant Degree Expanders (ps, pdf,ppt,bibtex)
    Noga Alon, Oded Schwartz and Asaf Shapira.
    A preliminary version appeared in
    ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 454-458, 2007.
    Accepted to Combinatorics, Probability and Computing.

  • An Explicit Construction of Quantum Expanders (ps, pdf,bibtex)
    Avraham Ben-Aroya, Oded Schwartz and Amnon Ta-Shma
    A preliminary version appeared in
    arXiv:0709.0911v1 [quant-ph], 2007.
  • Cooperative TSP (ps, pdf, ppt,bibtex)
    Adi Avidor,
    Amitai Armon and Oded Schwartz.
    A preliminary version appeared in
    Proc. of the
    14th Annual European Symposium on Algorithms (ESA), pp. 40-51, 2006.
    Journal version submitted.

  • On the Complexity of Approximating k-Set-Packing (ps, pdf, ppt,bibtex)
    Elad Hazan, Muli Safra and Oded Schwartz
    Computational Complexity, 15(1) pp. 20-39, 2006.
    A preliminary version appeared in
    Proc. of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2003.
  • On the Complexity of Approximating TSP with Neighborhoods and Related Problems (ps, pdf, ppt,bibtex)
    Muli Safra and Oded Schwartz.
    Computational Complexity, 14(4) pp.281 – 307, 2006.
    A preliminary version appeared in
    Proc. of the 11th Annual European Symposium on Algorithms (ESA), 2003.
    This paper contains results obtained in my Master's thesis (the constant inapproximability),
    as well as some newer results (NP-hardness for every constant factor).

Teaching – past