People

Group head

My research lies broadly in the theory of computing, algorithms and complexity. I'm exploring the limits of efficient computation and inference, both as a natural and a mathematical phenomenon. This includes computational and proof complexity, satisfiability, algebraic, logical and combinatorial approaches in complexity, and the theory of SAT- and constraint-solving.

Homepage

Postdocs

(alphabetic order)

Dr. Michal Garlik

I am interested in computational complexity and mathematical logic in general, and proof complexity in particular. Previously, I was a postdoc at St. Petersburg Department of Steklov Mathematical Institute, at the Polytechnic University of Catalonia and at the University of Warsaw. Before that, I was a PhD student at Charles University in Prague under the supervision of Jan Krajicek.

PhD Students

(alphabetic order)

Tal Elbaz

I am a PhD student at Imperial joining the computational complexity theory group under the supervision of Professor Iddo Tzameret. My research interests are in theoretical computer science, more precisely complexity theory, algorithm design and related areas. Previously, I attended McGill University where I completed both my Master's in computer science under the supervision of Professor Hamed Hatami and my Bachelor's in physics and computer science.

Nashlen Govindasamy

I am broadly interested in discrete mathematics and theoretical computer science. At present, I am a PhD student at Imperial College London and a member of the computational complexity theory group under the supervision of Iddo Tzameret. Before this, I did my MSc at the University of Oxford and my BSc at the University of Kwa Zulu-Natal.

Svyatolav Griaznov

Svyatoslav is a PhD student at the Department of Computing, Imperial College London, supervised by Prof. Iddo Tzameret. Prior to joining Imperial, he received MSc from St. Petersburg Academic University in TSC and BSc from St. Petersburg State University in Statistics. He was working as a Junior Researcher at PDMI RAS and was a researching fellow at the Institute of Mathematics of CAS (Prague) for a year. His research interests include circuit complexity, proof complexity, and extremal combinatorics. He strives to make progress in proving lower bounds on AC⁰[p] and AC⁰[p]-Frege.

MSc Students

Jiaqi Lu

Alumni

(alphabetic order)

Dr. Tuomas Hakoniemi

I'm postdoctoral researcher at Imperial College London, in the complexity of algorithms group at Imperial. My research interests are in computational complexity and mathematical logic, proof complexity in particular. Previously I was a PhD student at the Polytechnic University of Catalonia working under the supervision of Prof. Albert Atserias. Before that I've completed a master's degree in mathematics at the University of Helsinki and a master's degree in pure and applied logic at the University of Barcelona.

Luming Zhang

I am broadly interested in discrete mathematics and theoretical computer science. I am a current MSc student in Artificially Intelligence at Imperial and am fortunate to be supervised by Prof Iddo Tzameret. I completed my first MSc with Distinction in Mathematics and Foundations of Computer Science at Oxford under the supervision of Dr Dmitrii Pasechnik. Before that, I obtained my Bachelor of Mathematics degree in Combinatorics & Optimization, Pure Mathematics, and Psychology Minor at the University of Waterloo.

Visitors

2022: Robert Andrews
2023: Navid Talebanfard
2023: Hanlin Ren
2023: Albert Atserias
2024: Albert Atserias

Funding & Projects

Currently the group is supported by a five-year ERC (European Research Council) Consolidator Grant:

Efficient Proofs and Computation (EPRICOT): A Unified Algebraic Approach
Computational complexity lies at the heart of information and computer science. Its aim is to formally understand the boundary between problems that can be solved efficiently and those that cannot. This has many applications: new algorithms are important to make progress in domains such as machine learning and optimization, and new complexity lower bounds (namely, computational impossibility results) are essential to provably secure cryptography. Beyond practical applications, these questions reveal deep mathematical and natural phenomena. One of the prominent directions to attack the fundamental lower bound questions in complexity comes from the study of resource bounded provability, namely proof complexity. Its aim is to understand which problems possess solutions with short correctness proofs and which do not. Traditionally, proof complexity is concerned with propositional (Boolean) logic, and thus techniques from Boolean function complexity have had a huge impact on the field, driving many of its results and agendas. In this proposal we suggest to employ recent breakthroughs in the field of proof complexity exploiting algebraic approaches to broaden in a systematic way both the scope and techniques of proof complexity, going from weak settings to the very strong ones, up to the major open problems in the field and beyond. In particular, we propose to use algebraic notions and techniques such as structural algebraic circuit complexity, rank lower bounds, noncommutative and PI algebras, among others to significantly broaden the arsenal of lower bound tools as well as develop new models and insights into proofs, computation and their inter-relations. This project has potential for a transformative impact in theoretical computer science and beyond, with applications to unconditional computational lower bounds, which underlie secure cryptography and derandomization of probabilistic algorithms, as well as improved SAT- and constraint-solving heuristics.