| Publication | Date of Publication | Type |
|---|
Pinpointing computation with modular queries in the Boolean hierarchy
| 2024-07-05 | Paper |
Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
Computational Complexity | 2024-05-22 | Paper |
Factorization of polynomials given by arithmetic branching programs
| 2022-07-21 | Paper |
The complexity of poset games
Journal of Graph Algorithms and Applications | 2022-06-28 | Paper |
The complexity of regex crosswords
Information and Computation | 2022-06-13 | Paper |
Factorization of polynomials given by arithmetic branching programs
Computational Complexity | 2021-11-24 | Paper |
Isolating a vertex via lattices: polytopes with totally unimodular faces
| 2021-07-28 | Paper |
Bipartite perfect matching is in quasi-NC
SIAM Journal on Computing | 2021-06-29 | Paper |
Linear matroid intersection is in quasi-NC
Computational Complexity | 2021-05-25 | Paper |
Isolating a vertex via lattices: polytopes with totally unimodular faces
SIAM Journal on Computing | 2021-04-14 | Paper |
Exact perfect matching in complete graphs
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
Planarizing gadgets for perfect matching do not exist
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
Reductions to sets of low information content (extended abstract)
Automata, Languages and Programming | 2019-12-04 | Paper |
Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
| 2018-01-24 | Paper |
Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
Computational Complexity | 2017-12-18 | Paper |
The complexity of generating and checking proofs of membership
STACS 96 | 2017-11-16 | Paper |
A note on the search for \(k\) elements via quantum walk
Information Processing Letters | 2017-11-03 | Paper |
Bipartite perfect matching is in quasi-NC
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Linear matroid intersection is in quasi-NC
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Counting the number of perfect matchings in \(K_{5}\)-free graphs
Theory of Computing Systems | 2017-01-12 | Paper |
Game values and computational complexity: an analysis via black-white combinatorial games
Algorithms and Computation | 2016-01-11 | Paper |
Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace
Chicago Journal of Theoretical Computer Science | 2014-09-24 | Paper |
scientific article; zbMATH DE number 6146491 (Why is no real title available?)
| 2013-03-19 | Paper |
A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
Theoretical Computer Science | 2012-11-27 | Paper |
Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
| 2012-10-24 | Paper |
Planarizing Gadgets for Perfect Matching Do Not Exist
Mathematical Foundations of Computer Science 2012 | 2012-09-25 | Paper |
A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
Lecture Notes in Computer Science | 2011-08-17 | Paper |
The complexity of the inertia
Computational Complexity | 2011-02-18 | Paper |
The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
Theory of Computing Systems | 2010-10-06 | Paper |
The quantum query complexity of the determinant
Information Processing Letters | 2010-06-16 | Paper |
Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
Fundamentals of Computation Theory | 2009-10-20 | Paper |
On the Bipartite Unique Perfect Matching Problem
Automata, Languages and Programming | 2009-03-12 | Paper |
The Quantum Complexity of Group Testing
SOFSEM 2008: Theory and Practice of Computer Science | 2008-03-07 | Paper |
The Quantum Query Complexity of Algebraic Properties
Fundamentals of Computation Theory | 2008-02-26 | Paper |
The Polynomially Bounded Perfect Matching Problem Is in NC 2
STACS 2007 | 2007-09-03 | Paper |
ON THE MINIMAL POLYNOMIAL OF A MATRIX
International Journal of Foundations of Computer Science | 2005-10-19 | Paper |
scientific article; zbMATH DE number 2089958 (Why is no real title available?)
| 2004-08-12 | Paper |
The complexity of the characteristic and the minimal polynomial.
Theoretical Computer Science | 2003-08-17 | Paper |
scientific article; zbMATH DE number 1954385 (Why is no real title available?)
| 2003-07-28 | Paper |
scientific article; zbMATH DE number 1834664 (Why is no real title available?)
| 2002-11-25 | Paper |
The satisfiability problem for probabilistic ordered branching programs
Theory of Computing Systems | 2002-06-02 | Paper |
The Formula Isomorphism Problem
SIAM Journal on Computing | 2000-10-18 | Paper |
The computational complexity of equivalence and isomorphism problems
Lecture Notes in Computer Science | 2000-10-18 | Paper |
scientific article; zbMATH DE number 1414313 (Why is no real title available?)
| 2000-03-16 | Paper |
scientific article; zbMATH DE number 1354134 (Why is no real title available?)
| 1999-10-31 | Paper |
scientific article; zbMATH DE number 1335875 (Why is no real title available?)
| 1999-09-13 | Paper |
scientific article; zbMATH DE number 1335882 (Why is no real title available?)
| 1999-09-13 | Paper |
scientific article; zbMATH DE number 1332676 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 1999-09-08 | Paper |
scientific article; zbMATH DE number 1332670 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 1999-09-08 | Paper |
Functions computable with nonadaptive queries to NP
Theory of Computing Systems | 1998-08-24 | Paper |
Threshold Computation and Cryptographic Security
SIAM Journal on Computing | 1997-08-17 | Paper |
On sets bounded truth-table reducible to $P$-selective sets
RAIRO - Theoretical Informatics and Applications | 1997-04-13 | Paper |
On closure properties of \(\#\text{P}\) in the context of \(\text{PF} \circ \#\text{P}\)
Journal of Computer and System Sciences | 1997-03-31 | Paper |
Restricted information from nonadaptive queries to NP
Information and Computation | 1997-02-03 | Paper |
On the correlation of symmetric functions
Mathematical Systems Theory | 1996-09-09 | Paper |
NONDETERMINISTICALLY SELECTIVE SETS
International Journal of Foundations of Computer Science | 1996-08-13 | Paper |
On closure properties of GapP
Computational Complexity | 1995-05-14 | Paper |
A note on SpanP functions
Information Processing Letters | 1994-08-03 | Paper |
Complexity-Restricted Advice Functions
SIAM Journal on Computing | 1994-05-10 | Paper |
scientific article; zbMATH DE number 512798 (Why is no real title available?)
| 1994-03-10 | Paper |
