| Publication | Date of Publication | Type |
|---|
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
| 2024-11-28 | Paper |
CNF encodings of symmetric functions
Theory of Computing Systems | 2024-11-12 | Paper |
Super-cubic lower bound for generalized Karchmer-Wigderson games
| 2024-09-11 | Paper |
CNF encodings of parity
| 2024-08-06 | Paper |
A better-than-\(3\log(n)\) Depth lower bound for De Morgan formulas with restrictions on top gates
| 2024-07-05 | Paper |
If Edge Coloring is hard under SETH, then SETH is false
| 2024-05-29 | Paper |
Polynomial formulations as a barrier for reduction-based hardness proofs
| 2024-05-14 | Paper |
scientific article; zbMATH DE number 7740890 (Why is no real title available?)
| 2023-09-20 | Paper |
Toward better depth lower bounds: the XOR-KRW conjecture
| 2023-07-12 | Paper |
Collapsing Superstring Conjecture
| 2023-02-03 | Paper |
scientific article; zbMATH DE number 7561364 (Why is no real title available?)
| 2022-07-21 | Paper |
Computation of Hadwiger number and related contraction problems. Tight lower bounds
ACM Transactions on Computation Theory | 2022-03-22 | Paper |
scientific article; zbMATH DE number 7250152 (Why is no real title available?)
| 2020-09-22 | Paper |
Families with infants: speeding up algorithms for NP-hard problems using FFT
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Tight lower bounds on graph embedding problems
Journal of the ACM | 2018-05-17 | Paper |
Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
Lower bounds for the graph homomorphism problem
Automata, Languages, and Programming | 2015-10-27 | Paper |
New lower bounds on circuit size of multi-output functions
Theory of Computing Systems | 2015-07-20 | Paper |
Families with infants: a general approach to solve hard partition problems
Automata, Languages, and Programming | 2014-07-01 | Paper |
Solving SCS for bounded length strings in fewer than \(2^n\) steps
Information Processing Letters | 2014-04-30 | Paper |
Solving 3-superstring in \(3^{n/3}\) time
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
Approximating shortest superstring problem using de Bruijn graphs
Combinatorial Pattern Matching | 2013-06-14 | Paper |
Computing all MOD-functions simultaneously
Computer Science – Theory and Applications | 2012-09-10 | Paper |
A \(5n - o(n)\) lower bound on the circuit size over \(U _{2}\) of a linear Boolean function
Lecture Notes in Computer Science | 2012-08-14 | Paper |
