Research

My research interests include:

Property testing and other restricted input access models: The idea of giving approximate answers in situations where the input cannot be freely read in full. The prime example is when the number of read bits is restricted (property testing), but also approximate algorithms in other models, such as distributed message-passing ones, are considered. Testing of distributions through sampling also belongs here.

Graph theory and related combinatorial topics: My main topic of investigation before moving to CS. I am particularly fond of variations and applications of Szemer├ędi’s Regularity Lemma, and applications of combinatorics to property testing and other algorithms.

Formal logic and finite model theory: 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. I am particularly interested in combinatorial and algorithmic aspects.

Other topics: Never say never. Examples include Probabilistically Checkable Proofs, efficient database query evaluation algorithms, and so on.