| Publication | Date of Publication | Type |
|---|
Complexity of linear operators
Theory of Computing | 2026-02-10 | Paper |
Polynomial formulations as a barrier for reduction-based hardness proofs
ACM Transactions on Algorithms | 2025-11-03 | Paper |
| A better-than-3n lower bound for the circuit complexity of an explicit function | 2025-08-06 | Paper |
| 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 |
| CNF encodings of parity | 2024-08-06 | Paper |
| SAT-based circuit local improvement | 2024-08-06 | 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 |
Improving \(3N\) circuit complexity lower bounds
Computational Complexity | 2024-01-24 | Paper |
| scientific article; zbMATH DE number 7740890 (Why is no real title available?) | 2023-09-20 | Paper |
scientific article; zbMATH DE number 7650250 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
Collapsing Superstring Conjecture
(available as arXiv preprint) | 2023-02-03 | Paper |
Computing majority by constant depth majority circuits with low fan-in gates
Theory of Computing Systems | 2019-08-27 | Paper |
| Lower bounds for unrestricted Boolean circuits: open problems | 2018-11-28 | 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 |
On the limits of gate elimination
Journal of Computer and System Sciences | 2018-06-06 | Paper |
Tight lower bounds on graph embedding problems
Journal of the ACM | 2018-05-17 | Paper |
Computing majority by constant depth majority circuits with low fan-in gates
(available as arXiv preprint) | 2018-04-19 | Paper |
| Circuit size lower bounds and \#SAT upper bounds through a general framework | 2018-03-21 | Paper |
| On the limits of gate elimination | 2018-03-21 | Paper |
Gate elimination: circuit size lower bounds and \#SAT upper bounds
Theoretical Computer Science | 2018-03-12 | Paper |
Parameterized complexity of superstring problems
Algorithmica | 2017-11-09 | Paper |
Parameterized complexity of secluded connectivity problems
Theory of Computing Systems | 2017-10-12 | Paper |
Parameterized complexity of secluded connectivity problems
Theory of Computing Systems | 2017-10-12 | Paper |
| Parameterized complexity of secluded connectivity problems | 2017-07-13 | Paper |
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
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 |
Greedy Conjecture for Strings of Length 4
Combinatorial Pattern Matching | 2015-08-20 | Paper |
Parameterized complexity of superstring problems
Lecture Notes in Computer Science | 2015-08-20 | 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 |
New upper bounds for the problem of maximal satisfiability
Discrete Mathematics and Applications | 2012-03-23 | Paper |
An elementary proof of a \(3n - o(n)\) lower bound on the circuit complexity of affine dispersers
Mathematical Foundations of Computer Science 2011 | 2011-08-17 | Paper |
New upper bounds on the Boolean circuit complexity of symmetric functions
Information Processing Letters | 2010-09-07 | Paper |
A new approach to proving upper bounds for MAX-2-SAT
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Circuit complexity and multiplicative complexity of Boolean functions
Programs, Proofs, Processes | 2010-07-29 | Paper |
On convex complexity measures
Theoretical Computer Science | 2010-04-15 | Paper |
| Complexity of semialgebraic proofs with restricted degree of falsity | 2009-10-12 | Paper |
On covering graphs by complete bipartite subgraphs
Discrete Mathematics | 2009-06-23 | Paper |
New Bounds for MAX-SAT by Clause Learning
Computer Science – Theory and Applications | 2008-06-03 | Paper |
Complexity of Semialgebraic Proofs with Restricted Degree of Falsity
Lecture Notes in Computer Science | 2007-09-04 | Paper |
A \(2^{|E|/4}\)-time algorithm for MAX-CUT
Journal of Mathematical Sciences (New York) | 2006-01-03 | Paper |
An upper bound \(O(2^{0.16254n})\) for exact 3-satisfiability: a simpler proof
Journal of Mathematical Sciences (New York) | 2006-01-03 | Paper |
Theory and Applications of Satisfiability Testing
Lecture Notes in Computer Science | 2005-12-15 | Paper |
Parameterized and Exact Computation
Lecture Notes in Computer Science | 2005-08-23 | Paper |
| scientific article; zbMATH DE number 2187722 (Why is no real title available?) | 2005-07-20 | Paper |
