| Publication | Date of Publication | Type |
|---|
| Shrinkage of decision lists and DNF formulas | 2026-04-15 | Paper |
| Tree-depth and the formula complexity of subgraph isomorphism | 2025-08-12 | Paper |
| Exponential lower bounds for monotone span programs | 2025-08-06 | Paper |
| An average-case depth hierarchy theorem for Boolean circuits | 2025-08-05 | Paper |
| The average sensitivity of bounded-depth formulas | 2025-08-05 | Paper |
| On the AC0 complexity of subgraph isomorphism | 2025-08-05 | Paper |
| The monotone complexity of k-clique on random graphs | 2025-04-29 | Paper |
| Symmetric formulas for products of permutations | 2024-09-25 | Paper |
Tree-Depth and the Formula Complexity of Subgraph Isomorphism
SIAM Journal on Computing | 2023-04-04 | Paper |
Monotone circuit lower bounds from robust sunflowers
Algorithmica | 2022-12-08 | Paper |
Thresholds in the lattice of subspaces of \(\mathbb{F}_q^n\)
(available as arXiv preprint) | 2022-10-13 | Paper |
Monotone circuit lower bounds from robust sunflowers
LATIN 2020: Theoretical Informatics | 2022-10-13 | Paper |
| Criticality of regular formulas | 2022-07-27 | Paper |
A polynomial excluded-minor approximation of treedepth
Journal of the European Mathematical Society (JEMS) | 2022-03-29 | Paper |
| Shrinkage of Decision Lists and DNF Formulas | 2020-12-09 | Paper |
| Coin-flipping magic | 2020-11-10 | Paper |
Lower bounds for subgraph isomorphism
Proceedings of the International Congress of Mathematicians (ICM 2018) | 2020-09-22 | Paper |
| Separation of \(\mathrm{AC}^0[\oplus]\) formulas and circuits | 2020-05-27 | Paper |
| Subspace-invariant \(\mathrm{AC}^0\) formulas | 2020-05-27 | Paper |
Tree-depth and the Formula Complexity of Subgraph Isomorphism
(available as arXiv preprint) | 2020-04-28 | Paper |
Thresholds in the Lattice of Subspaces of $(\mathbb F_q)^n$
(available as arXiv preprint) | 2019-10-01 | Paper |
Subspace-invariant \(\mathrm{AC}^0\) formulas
(available as arXiv preprint) | 2019-08-06 | Paper |
Formulas versus Circuits for Small Distance Connectivity
SIAM Journal on Computing | 2018-11-07 | Paper |
The average sensitivity of bounded-depth formulas
Computational Complexity | 2018-08-03 | Paper |
An average-case depth hierarchy theorem for Boolean circuits
Journal of the ACM | 2018-05-17 | Paper |
scientific article; zbMATH DE number 6866317 (Why is no real title available?)
(available as arXiv preprint) | 2018-05-03 | Paper |
| A polynomial excluded-minor approximation of treedepth | 2018-03-15 | Paper |
| scientific article; zbMATH DE number 6829287 (Why is no real title available?) | 2018-01-24 | Paper |
The query complexity of witness finding
Theory of Computing Systems | 2017-10-20 | Paper |
Poly-logarithmic Frege depth lower bounds via an expander switching lemma
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
SIAM Journal on Computing | 2017-05-30 | Paper |
Formulas vs. circuits for small distance connectivity
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
An optimal decomposition algorithm for tree edit distance
ACM Transactions on Algorithms | 2014-11-18 | Paper |
The query complexity of witness finding
Computer Science - Theory and Applications | 2014-06-24 | Paper |
The monotone complexity of \(k\)-clique on random graphs
SIAM Journal on Computing | 2014-06-04 | Paper |
A Tight Upper Bound on the Number of Variables for Average-Case k-Clique on Ordered Graphs
Logic, Language, Information and Computation | 2012-09-21 | Paper |
The homomorphism domination exponent
European Journal of Combinatorics | 2011-11-29 | Paper |
Choiceless computation and symmetry
Fields of Logic and Computation | 2010-09-03 | Paper |
| scientific article; zbMATH DE number 5605066 (Why is no real title available?) | 2009-09-19 | Paper |
Ehrenfeucht-Fraïssé Games on Random Structures
Logic, Language, Information and Computation | 2009-07-02 | Paper |
| scientific article; zbMATH DE number 5485586 (Why is no real title available?) | 2009-01-05 | Paper |
Homomorphism preservation theorems
Journal of the ACM | 2008-12-21 | Paper |
Interactive Small-Step Algorithms I: Axiomatization
Logical Methods in Computer Science | 2008-04-01 | Paper |
Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem
Logical Methods in Computer Science | 2008-04-01 | Paper |
Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
Annals of Pure and Applied Logic | 2008-03-28 | Paper |
An Optimal Decomposition Algorithm for Tree Edit Distance
Automata, Languages and Programming | 2007-11-28 | Paper |
Successor-invariant first-order logic on finite structures
Journal of Symbolic Logic | 2007-07-09 | Paper |
Semantic essence of AsmL
Theoretical Computer Science | 2005-11-01 | Paper |
Formal Methods for Components and Objects
Lecture Notes in Computer Science | 2005-08-22 | Paper |
