Bruno Loff

Alexey Milovanov

Electron. Colloquium Comput. Complex., 2024

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity.

[BibT_eX]

[DOI]

Pavel Dvorák

Suhail Sherif

CoRR, 2024

Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games.

[BibT_eX]

[DOI]

Mateusz Skomra

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2022

Memory Compression with Quantum Random-Access Gates.

[BibT_eX]

[DOI]

Proceedings of the 17th Conference on the Theory of Quantum Computation, 2022

Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Hardness of Constant-round Communication Complexity.

[BibT_eX]

[DOI]

Shuichi Hirahara

Rahul Ilango

Electron. Colloquium Comput. Complex., 2021

2020

The computational power of parsing expression grammars.

[BibT_eX]

[DOI]

Nelma Moreira

Rogério Reis

J. Comput. Syst. Sci., 2020

NP-Hardness of Circuit Minimization for Multi-Output Functions.

[BibT_eX]

[DOI]

Rahul Ilango

Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2020

Lower Bounds for Semi-adaptive Data Structures via Corruption.

[BibT_eX]

[DOI]

Pavel Dvorák

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

2019

Simulation Theorems via Pseudo-random Properties.

[BibT_eX]

[DOI]

Comput. Complex., 2019

2018

Catalytic Space: Non-determinism and Hierarchy.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

Lifting Theorems for Equality.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

2017

Simulation Beats Richness: New Data-Structure Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Composition and Simulation Theorems via Pseudo-random Properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Simulation Theorems via Pseudorandom Properties.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Lower Bounds for Elimination via Weak Regularity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Towards a Reverse Newman's Theorem in Interactive Information Complexity.

[BibT_eX]

[DOI]

Nikolai K. Vereshchagin

Algorithmica, 2016

2015

Hardness of Approximation for Knapsack Problems.

[BibT_eX]

[DOI]

Harry Buhrman

Leen Torenvliet

Theory Comput. Syst., 2015

2014

Computing with a full memory: Catalytic space.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

Learning Reductions to Sparse Sets.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

2012

Monotonicity Constraints in Characterizations of PSPACE.

[BibT_eX]

[DOI]

Amir M. Ben-Amram

Isabel Oitavem

J. Log. Comput., 2012

Towards a Reverse Newman's Theorem in Interactive Information Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Reductions to the set of random strings: the resource-bounded case.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

2010

Derandomizing from Random Strings.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Five Views of Hypercomputation.

[BibT_eX]

[DOI]

Int. J. Unconv. Comput., 2009

A foundation for real recursive function theory.

[BibT_eX]

[DOI]

Jerzy Mycka

Ann. Pure Appl. Log., 2009

2008

Oracles and Advice as Measurements.

[BibT_eX]

[DOI]

Proceedings of the Unconventional Computing, 7th International Conference, 2008

On the Complexity of Measurement in Classical Physics.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2008

2007

Computability on reals, infinite limits and differential equations.

[BibT_eX]

[DOI]

Jerzy Mycka

Appl. Math. Comput., 2007

The New Promise of Analog Computation.

[BibT_eX]

[DOI]