SIGACT News Complexity Theory Column 127 and 128

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!

Authors

Publication Details

Journal
ACM SIGACT News
Published
2026-03-31
DOI
https://doi.org/10.1145/3802807.3802812
Primary Topic
Quantum Computing Algorithms and Architecture
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

SIGACT News Complexity Theory Column 127 and 128

Ben Lee Volk
ACM SIGACT News
Quantum Computing Algorithms and Architecture
article

SIGACT News Complexity Theory Column 127 and 128

Ben Lee Volk
article en

Abstract

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 NewsVol. 57(1)
Openalex Percentile: Top 5%
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.