The project

We are broadly interested in answering the following question:

Fix some computational model. Now suppose we are given a full description of a computational problem, and wish to find an efficient algorithm for solving it, or at least to estimate its computational complexity, in the said model… How hard is this algorithm-finding/complexity-estimation task?

We are interested in answering this question for different computational models, and especially interested in understanding when is the above task NP-hard?

We wish to study this question for decision trees, communication protocols, Boolean circuits and formulae, data structure problems, algebraic models, streaming models, various combinatorial complexity measures of complexity such as certificate complexity, partition number, etc, etc.

We will also work in various follow-up questions that arose when thinking about these things. And, more broadly, we are interested in proving unconditional lower-bounds of any kind, and especially in understanding the computational complexity (the “naturalness”) of the hardness-implying properties used in such proofs.