Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM SIGACT News

SIGACT News Complexity Theory Column 107

Lane A. Hemaspaandra

Published Dec 14, 2020• 0 citations
Publisher

Abstract

Warmest thanks to Mark Bun and Justin Thaler for their terri c article, \Approximate Degree in Classical and Quantum Computing." And, amazingly, they made the time to craft it during a time of worldwide pandemic|wow!
DOI
10.1145/3444815.3444824

Related papers

Concept and Algorithm of Quantum Computing During Pandemic Situation of COVID-19

Nirupma Pathak, Neeraj Kumar Misra, Bandan Kumar Bhoi +1 more

Smart innovation, systems and technologies•Sep 3, 2021•4 citations

SIGACT News Complexity Theory Column 110

Lane A. Hemaspaandra

My deepest thanks to Beatrice and Carlo for their fascinating article, Quantum Finite Automata: From Theory to Practice. Regarding the extent to which their article brings to life both parts of its subtitle... wow! And I think Section 4 is an absolute first for this column; please don't miss it!

ACM SIGACT News•Oct 17, 2021•0 citations

SIGACT News Complexity Theory Column 119

Ben Lee Volk

After a short break, the complexity theory column is back! In this issue, Sevag Gharibian introduces us to the multifaceted nature of Quantum NP and its relation to Snow White (yes, it all makes sense if you read the column). Thanks a lot to Sevag for his dedication and thoroughness and the effort he put into his fantastic contribution.

ACM SIGACT News•Dec 29, 2023•0 citations

One complexity theorist's view of quantum computing

Lance Fortnow

Theoretical Computer Science•Jan 1, 2003•80 citations

SIGACT News Complexity Theory Column 127 and 128

Ben Lee Volk

Dear Readers, After a short hiatus, the complexity theory column is back with a double feature! In this issue, we present a column by Mitali Bafna on Size-Efficient PCPs from High-Dimensional Expanders, and a column by Fernando Granha Jeronimo, Itai Leigh and Pei Wu on the landscape of complexity classes surrounding QMA(2). Both columns are excellent, and I am sure you will find them both enjoyable and enlightening. Many thanks to the authors for their hard work! What's coming up next in the pipeline? If all goes according to plan, we will feature guest columns by Geoffroy Couteau; Jesse Goodman (on seedless extractors); Davi Castro-Silva, Arkopal Dutt, and Tom Gur (on connections between additive combinatorics and quantum complexity theory); Debarati Das; and Jeroen Zuiddam (on matrix multiplication, moment polytopes and asymptotic spectra). Stay tuned for upcoming issues of SIGACT News!

ACM SIGACT News•Mar 31, 2026•0 citations

On the measurement of entanglement degree in frequency variables

Valentina Caricato, G. Brida, Marco Genovese +3 more

•Jan 1, 2008•0 citations
Dear Readers, After a short hiatus, the complexity theory column is back with a double feature! In this issue, we present a column by Mitali Bafna on Size-Efficient PCPs from High-Dimensional Expanders, and a column by Fernando Granha Jeronimo, Itai Leigh and Pei Wu on the landscape of complexity classes surrounding QMA(2). Both columns are excellent, and I am sure you will find them both enjoyable and enlightening. Many thanks to the authors for their hard work! What's coming up next in the pipeline? If all goes according to plan, we will feature guest columns by Geoffroy Couteau; Jesse Goodman (on seedless extractors); Davi Castro-Silva, Arkopal Dutt, and Tom Gur (on connections between additive combinatorics and quantum complexity theory); Debarati Das; and Jeroen Zuiddam (on matrix multiplication, moment polytopes and asymptotic spectra). Stay tuned for upcoming issues of SIGACT News!