Luke Schaeffer

Stefan Zorcic

CoRR, 2024

2023

On the Rational Degree of Boolean Functions and Applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

2022

The Classification of Clifford Gates over Qubits.

[BibT_eX]

[DOI]

Quantum, 2022

Sample-optimal classical shadows for pure states.

[BibT_eX]

[DOI]

Hakop Pashayan

CoRR, 2022

The First-Order Theory of Binary Overlap-Free Words is Decidable.

[BibT_eX]

[DOI]

CoRR, 2022

Decidability for Sturmian Words.

[BibT_eX]

[DOI]

Proceedings of the 30th EACSL Annual Conference on Computer Science Logic, 2022

2021

Ostrowski-automatic sequences: Theory and applications.

[BibT_eX]

[DOI]

Aseem R. Baranwal

Theor. Comput. Sci., 2021

Interactive quantum advantage with noisy, shallow Clifford circuits.

[BibT_eX]

[DOI]

Nathan Ju

CoRR, 2021

2020

Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

A Note on Key Agreement and Non-Interactive Commitments.

[BibT_eX]

[DOI]

Alex Lombardi

IACR Cryptol. ePrint Arch., 2019

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

A Quantum Query Complexity Trichotomy for Regular Languages.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2019

Interactive shallow Clifford circuits: quantum advantage against NC<sup>1</sup> and beyond.

[BibT_eX]

[DOI]

CoRR, 2019

2017

Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

2016

Decision algorithms for Fibonacci-automatic Words, I: Basic results.

[BibT_eX]

[DOI]

Hamoon Mousavi

RAIRO Theor. Informatics Appl., 2016

Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2016

New Hardness Results for the Permanent Using Linear Optics.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

The Classification of Stabilizer Operations over Qubits.

[BibT_eX]

[DOI]

CoRR, 2016

Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences.

[BibT_eX]

[DOI]

Electron. J. Comb., 2016

2015

Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

The Classification of Reversible Bit Operations.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2015

Closed, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences.

[BibT_eX]

[DOI]

CoRR, 2015

A New Approach to the Paperfolding Sequences.

[BibT_eX]

[DOI]

Proceedings of the Evolving Computability - 11th Conference on Computability in Europe, 2015

A Physically Universal Quantum Cellular Automaton.

[BibT_eX]

[DOI]

Proceedings of the Cellular Automata and Discrete Complex Systems, 2015

2014

Avoiding Three Consecutive Blocks of the Same Size and Same Sum.

[BibT_eX]

[DOI]

J. ACM, 2014

A Physically Universal Cellular Automaton.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance.

[BibT_eX]

[DOI]

CoRR, 2014

2013

Ostrowski Numeration and the Local Period of Sturmian Words.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2013

Subword Complexity and k-Synchronization.

[BibT_eX]

[DOI]

Daniel Goc

Proceedings of the Developments in Language Theory - 17th International Conference, 2013

2012

The Critical Exponent is Computable for Automatic Sequences.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2012

An Improved Lower Bound for Stack Sorting

[BibT_eX]

[DOI]

CoRR, 2012

The Subword Complexity of k-Automatic Sequences is k-Synchronized

[BibT_eX]

[DOI]

Daniel Goc