| Publication | Date of Publication | Type |
|---|
| Noisy decoding by shallow circuits with parities: classical and quantum (extended abstract) | 2025-11-04 | Paper |
| A qubit, a coin, and an advice string walk into a relational problem | 2025-11-04 | Paper |
| Quantum lower bounds by polynomials | 2025-10-29 | Paper |
| Quantum majority vote | 2024-09-25 | Paper |
| Memory compression with quantum random-access gates | 2024-06-27 | Paper |
scientific article; zbMATH DE number 7829263 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
| Quantum majority vote | 2022-11-21 | Paper |
Resource-bounded Kolmogorov complexity revisited
Lecture Notes in Computer Science | 2022-11-09 | Paper |
scientific article; zbMATH DE number 7559121 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-18 | Paper |
High entropy random selection protocols
Algorithmica | 2021-03-26 | Paper |
On the cutting edge of relativization: The resource bounded injury method
Automata, Languages and Programming | 2019-04-29 | Paper |
Sparse selfreducible sets and nonuniform lower bounds
Algorithmica | 2019-01-11 | Paper |
The first peptides: the evolutionary transition between prebiotic amino acids and early proteins
Journal of Theoretical Biology | 2018-12-11 | Paper |
Results on resource-bounded measure
Automata, Languages and Programming | 2018-07-04 | Paper |
Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication
(available as arXiv preprint) | 2018-05-03 | Paper |
Catalytic space: non-determinism and hierarchy
Theory of Computing Systems | 2018-03-01 | Paper |
| scientific article; zbMATH DE number 6829365 (Why is no real title available?) | 2018-01-24 | Paper |
On the sparse set conjecture for sets with low density
STACS 95 | 2017-12-04 | Paper |
Compressibility and resource bounded measure
STACS 96 | 2017-11-16 | Paper |
The complexity of generating and checking proofs of membership
STACS 96 | 2017-11-16 | Paper |
Long-lived renaming made fast
Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing - PODC '95 | 2017-09-29 | Paper |
Round elimination in exact communication complexity
(available as arXiv preprint) | 2017-07-12 | Paper |
The garden-hose model
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Entanglement-assisted zero-error source-channel coding
IEEE Transactions on Information Theory | 2017-04-28 | Paper |
On the parallel repetition of multi-player games: the no-signaling case
(available as arXiv preprint) | 2017-03-13 | Paper |
Quantum communication complexity advantage implies violation of a Bell inequality
Proceedings of the National Academy of Sciences | 2017-02-16 | Paper |
Distinguishing two probability ensembles with one sample from each ensemble
Theory of Computing Systems | 2017-01-12 | Paper |
Towards a reverse Newman's theorem in interactive information complexity
Algorithmica | 2016-11-29 | Paper |
Optimal routing tables
Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing - PODC '96 | 2015-09-11 | Paper |
Computing with a full memory: catalytic space
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Hardness of approximation for knapsack problems
Theory of Computing Systems | 2015-05-29 | Paper |
Near-optimal and explicit Bell inequality violations
Theory of Computing | 2014-10-06 | Paper |
Reductions to the set of random strings: the resource-bounded case
Logical Methods in Computer Science | 2014-09-05 | Paper |
Violating the Shannon capacity of metric graphs with entanglement
Proceedings of the National Academy of Sciences | 2014-07-25 | Paper |
Zero-error source-channel coding with entanglement
The Seventh European Conference on Combinatorics, Graph Theory and Applications | 2014-06-11 | Paper |
Position-based quantum cryptography: impossibility and constructions
SIAM Journal on Computing | 2014-06-04 | Paper |
scientific article; zbMATH DE number 6292744 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 2014-05-07 | Paper |
Learning Reductions to Sparse Sets
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
On the importance of having an identity or, is consensus really universal?
Distributed Computing | 2013-06-07 | Paper |
Learning parities in the mistake-bound model
Information Processing Letters | 2013-04-04 | Paper |
Reductions to the set of random strings: the resource-bounded case
Lecture Notes in Computer Science | 2012-09-25 | Paper |
Limit on nonlocality in any world in which communication complexity is not trivial
Physical Review Letters | 2011-12-26 | Paper |
Security of quantum bit string commitment depends on the information measure
Physical Review Letters | 2011-12-26 | Paper |
All Schatten spaces endowed with the Schur product are \(Q\)-algebras
Journal of Functional Analysis | 2011-12-14 | Paper |
A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
Communications in Mathematical Physics | 2011-08-23 | Paper |
Position-based quantum cryptography: impossibility and constructions
Advances in Cryptology – CRYPTO 2011 | 2011-08-12 | Paper |
Non-uniform reductions
Theory of Computing Systems | 2010-10-06 | Paper |
Quantum verification of matrix products
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Does the polynomial hierarchy collapse if onto functions are invertible?
Theory of Computing Systems | 2010-03-05 | Paper |
| A Post's program for complexity theory. | 2009-09-19 | Paper |
Unconditional Lower Bounds against Advice
Automata, Languages and Programming | 2009-07-14 | Paper |
Quantum zero-error algorithms cannot be composed
Information Processing Letters | 2009-04-28 | Paper |
High Entropy Random Selection Protocols
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
Quantum Property Testing
SIAM Journal on Computing | 2008-10-28 | Paper |
Inverting Onto Functions and Polynomial Hierarchy
Computer Science – Theory and Applications | 2008-06-03 | Paper |
Implications of superstrong non-locality for cryptography
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | 2008-05-22 | Paper |
Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds
STACS 2006 | 2008-03-19 | Paper |
Quantum lower bounds by polynomials
Journal of the ACM | 2008-02-11 | Paper |
Mathematical Foundations of Computer Science 2003
Lecture Notes in Computer Science | 2007-12-07 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Robust polynomials and quantum algorithms
Theory of Computing Systems | 2007-08-23 | Paper |
Individual communication complexity
Journal of Computer and System Sciences | 2007-08-23 | Paper |
Enumerations of the Kolmogorov function
Journal of Symbolic Logic | 2006-08-03 | Paper |
Power from Random Strings
SIAM Journal on Computing | 2006-06-01 | Paper |
Language compression and pseudorandom generators
Computational Complexity | 2006-02-08 | Paper |
New Computational Paradigms
Lecture Notes in Computer Science | 2006-01-11 | Paper |
What can be efficiently reduced to the Kolmogorov-random strings?
Annals of Pure and Applied Logic | 2005-12-29 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
Quantum Algorithms for Element Distinctness
SIAM Journal on Computing | 2005-09-16 | Paper |
Some results on derandomization
Theory of Computing Systems | 2005-04-19 | Paper |
Mutual search
Journal of the ACM | 2005-01-25 | Paper |
scientific article; zbMATH DE number 2079374 (Why is no real title available?)
(available as arXiv preprint) | 2004-07-28 | Paper |
scientific article; zbMATH DE number 1775389 (Why is no real title available?)
(available as arXiv preprint) | 2004-01-27 | Paper |
| scientific article; zbMATH DE number 1962843 (Why is no real title available?) | 2003-08-11 | Paper |
| scientific article; zbMATH DE number 1962815 (Why is no real title available?) | 2003-08-11 | Paper |
Complexity measures and decision tree complexity: a survey.
Theoretical Computer Science | 2003-01-21 | Paper |
| scientific article; zbMATH DE number 1775405 (Why is no real title available?) | 2002-08-01 | Paper |
A lower bound for quantum search of an ordered list
Information Processing Letters | 2002-07-25 | Paper |
| scientific article; zbMATH DE number 1754652 (Why is no real title available?) | 2002-06-12 | Paper |
Two oracles that force a big crunch
Computational Complexity | 2002-05-05 | Paper |
Resource-bounded Kolmogorov complexity revisited
SIAM Journal on Computing | 2002-04-23 | Paper |
Compressibility and resource bounded measure
SIAM Journal on Computing | 2002-04-23 | Paper |
The communication complexity of enumeration, elimination, and selection
Journal of Computer and System Sciences | 2002-04-11 | Paper |
| scientific article; zbMATH DE number 1696671 (Why is no real title available?) | 2002-01-28 | Paper |
Time and space bounds for reversible simulation
Journal of Physics A: Mathematical and General | 2002-01-27 | Paper |
| scientific article; zbMATH DE number 1512076 (Why is no real title available?) | 2001-09-04 | Paper |
Quantum entanglement and communication complexity
SIAM Journal on Computing | 2001-03-19 | Paper |
Randomness is hard
SIAM Journal on Computing | 2001-03-19 | Paper |
| scientific article; zbMATH DE number 1860690 (Why is no real title available?) | 2001-01-01 | Paper |
| scientific article; zbMATH DE number 1500532 (Why is no real title available?) | 2000-09-04 | Paper |
New applications of the incompressibility method. II
Theoretical Computer Science | 2000-06-04 | Paper |
| scientific article; zbMATH DE number 1335898 (Why is no real title available?) | 2000-05-14 | Paper |
| scientific article; zbMATH DE number 1335876 (Why is no real title available?) | 2000-05-04 | Paper |
| scientific article; zbMATH DE number 1335891 (Why is no real title available?) | 2000-05-04 | Paper |
| scientific article; zbMATH DE number 1306884 (Why is no real title available?) | 2000-04-26 | Paper |
| scientific article; zbMATH DE number 1405647 (Why is no real title available?) | 2000-04-25 | Paper |
Kolmogorov Random Graphs and the Incompressibility Method
SIAM Journal on Computing | 2000-03-19 | Paper |
Separating Complexity Classes Using Autoreducibility
SIAM Journal on Computing | 2000-03-19 | Paper |
Two queries
Journal of Computer and System Sciences | 2000-01-17 | Paper |
Hard sets are hard to find
Journal of Computer and System Sciences | 2000-01-17 | Paper |
Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method
SIAM Journal on Computing | 1999-10-28 | Paper |
| scientific article; zbMATH DE number 1222922 (Why is no real title available?) | 1999-10-10 | Paper |
| scientific article; zbMATH DE number 1335875 (Why is no real title available?) | 1999-09-13 | Paper |
| scientific article; zbMATH DE number 1318518 (Why is no real title available?) | 1999-08-08 | Paper |
| scientific article; zbMATH DE number 1304314 (Why is no real title available?) | 1999-06-17 | Paper |
| scientific article; zbMATH DE number 1303590 (Why is no real title available?) | 1999-06-17 | Paper |
Functions computable with nonadaptive queries to NP
Theory of Computing Systems | 1998-08-24 | Paper |
Splittings, Robustness, and Structure of Complete Sets
SIAM Journal on Computing | 1998-05-10 | Paper |
An excursion to the Kolmogorov random strings
Journal of Computer and System Sciences | 1997-08-03 | Paper |
\(p\)-selective self-reducible sets: a new characterization of P
Journal of Computer and System Sciences | 1997-03-31 | Paper |
Random strings make hard instances
Journal of Computer and System Sciences | 1996-11-27 | Paper |
SPARSE Reduces Conjunctively to TALLY
SIAM Journal on Computing | 1995-11-01 | Paper |
| scientific article; zbMATH DE number 512826 (Why is no real title available?) | 1994-04-07 | Paper |
| scientific article; zbMATH DE number 512801 (Why is no real title available?) | 1994-03-10 | Paper |
The relative power of logspace and polynomial time reductions
Computational Complexity | 1994-01-19 | Paper |
| scientific article; zbMATH DE number 176522 (Why is no real title available?) | 1993-05-18 | Paper |
Completeness for nondeterministic complexity classes
Mathematical Systems Theory | 1992-06-26 | Paper |
Noisy decoding by shallow circuits with parities: classical and quantum
(available as arXiv preprint) | N/A | Paper |
