Computer scientist, working on theoretical questions that are motivated by practical problems. My thesis was on tractable classes of constraint satisfaction problems, and I have also worked on containment of conjunctive database queries, the macroscope model of communication complexity, lower bounds for streaming, and bounds on parallelism.
Edinburgh, United Kingdom
Member for 6 years, 11 months
5 profile views
Last seen Nov 15 at 6:49
- Theoretical Computer Science 18.2k 18.2k 33 gold badges5656 silver badges141141 bronze badges
- Computer Science 2.9k 2.9k 11 gold badge1414 silver badges3333 bronze badges
- MathOverflow 2.1k 2.1k 11 gold badge1414 silver badges2828 bronze badges
- TeX - LaTeX 1.8k 1.8k 22 gold badges2222 silver badges3131 bronze badges
- Mathematics 1.1k 1.1k 1010 silver badges2525 bronze badges
- View network profile →
Top network posts
- 180 What packages do people load by default in LaTeX?
- 137 Major unsolved problems in theoretical computer science?
- 84 Animation in PDF presentations, without Adobe Reader?
- 54 Can one amplify P=NP beyond P=PH?
- 51 Dinner-table description of theoretical computer science?
- 47 Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming
- 45 Generalized Ladner's Theorem
- View more network posts →