Eldar Fischer's
Home Page 
Eldar Fischer's
Home Page
If you have difficulties loading parts of the site: This probably means that you are accessing the site through the "˜eldar" web address using Windows XP. Please try this address instead.
Publication list: Click here (most articles are available for download).
Property testing: A topic in which I am very involved in the last years. Basically this deals with an approximation notion that for many problems allows for the construction algorithms that can resolve it without reading the entire input, and many times have a correspondingly sublinear running time. This is a relatively young topic that is currently enjoying rapid growth.
Graph theory: Mathematically speaking I grew up on graph theory, as my publications from the time of my Ph.D. studies would confirm. I am still very interested in this topic, and especially in applications of the Regularity Lemma. I am also interested in applications of combinatorial theory, and graph theory in particular, to property testing, logic (see below), and computational theory in general.
Formal logic and finite model theory: This is an exciting field that has a lot in common with combinatorial theory. It basically deals with asking what structures can be easily described, and what properties can be easily calculated, within a given language and under a given set of restrictions.
Probabilistically Checkable Proofs: As the name suggests, this deals with proof protocols that are easy (in that they take only a few queries) to verify, though the theory of constructing such proofs is not easy at all. In essence the existence of an easy to verify proof may mean that a certain approximation problem is hard, because such a proof may serve as a reduction to an NP-Hard problem. This has some connections with property testing, since a verification of a proof can start with a property test for a feature that once guaranteed makes the proof easier to verify.
Other topics in computational theory and combinatorics: The above list of course does not exclude other topics from catching my attention. In particular, I have also some interests in statistical deduction algorithms, coding theory, and database query evaluation algorithms.
Every winter semester (from 2002-2003) I gave the course Probabilistic Methods and Algorithms; there is a small preparatory work for this course, so please head for its page for details. Next year it will also be given, but it will be in the 2011 Spring semester instead.
In the 2009 Spring semester I tried something new, an advanced seminar revolving around the reading and analysis of a hard research paper(s). Next time it will be given in the 2010-2011 winter semester. If you are interested in participating, please email me.
Every spring semester from 2002 to 2008 I gave a property testing seminar. I will give it next in the 2010 spring semester, after skipping a year. Property testing is one of my primary research interests so feel free to browse the seminar page also if you are not planning to participate in such a seminar.
I have taught the course Database management systems (236363) for the seventh time in the 2009-2010 Winter semester, and will likely teach it again next year.
I have managed (but not taught) Introduction to computing (234112) in the 2008-2009 Winter semester.
I have also given the course File systems (234322) in the 2003 Spring semester.