Associate Professor Eldar Fischer
- Contact information
- Office Hours:
- Thursday, 14:30-15:30
- Research interests
- Efficiency of calculations: Especially property testing, statisticaldeductions, and probabilistically checkable proofs; Combinatorics:Especially graph theory, regularity theorems in combinatorialstructures, and applications to algorithms; Logic in Computer Science:Logical characterization of properties for which there exist efficientalgorithms or desirable combinatorial aspects.
- Selected publications
I. Dinur, E. Fischer, G. Kindler, R. Raz and S. Safra, PCP characterizations of NP: Towards a polynomially-small error-probability, Proceedings of the 31st STOC (1999), 29-40.
N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), 451-476 (a preliminary version appeared in Proceedings of the 40th FOCS, 1999).
E. Fischer and I. Newman, Testing of matrix properties, Proceedings of the 33rd STOC (2001), 286-295.
E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science 75 (2001), 97-126.
Also in: Current Trends in Theoretical Computer Science: The Challenge of the New Century, G. Paun, G. Rozenberg and A. Salomaa (editors), World Scientific Publishing (2004), Vol. I 229-264.
E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld and A. Samorodnitsky, Monotonicity testing over general poset domains, Proceedings of the 34th STOC (2002), 474-483.
E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Testing juntas, Journal of Computer and System Sciences 68 2004, 43rd FOCS (2002) special issue, 753-787.
E. Fischer, The Specker-Blatter theorem does not hold for quaternary relations, Journal of Combinatorial Theory Series A 103 (2003), 121-136.
E. Fischer and J. A. Makowsky, On spectra of sentences of monadic second order logic with counting, Journal of Symbolic Logic 69 (2004), 617-640.
E. Fischer and L. Fortnow, Tolerant versus intolerant testing for Boolean properties, Proceedings of the 21th CCC (2005), 135-140.
N. Alon, E. Fischer, I. Newman and A. Shapira A combinatorial characterization of the testable graph properties: It's all about regularity, Proceedings of the 38th STOC (2006), 251-260, invited for the special issue.