Powered by
56th Annual ACM Symposium on Theory of Computing (STOC 2024),
June 24–28, 2024,
Vancouver, BC, Canada
Frontmatter
Papers
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland
, Daniel Lokshtanov
,
Tomáš Masařík , Marcin Pilipczuk
, Michał Pilipczuk
, and Paweł Rzążewski
(University of California, Santa Barbara, USA; University of Warsaw, Poland; IT University Copenhagen, Denmark; Warsaw University of Technology, Poland)
Preprint
A New Information Complexity Measure for Multi-pass Streaming with Applications
Mark Braverman
, Sumegha Garg
, Qian Li
, Shuo Wang
, David P. Woodruff
, and Jiapeng Zhang
(Princeton University, USA; Rutgers University, USA; Shenzhen Research Institute of Big Data, China; Shanghai Jiao Tong University, China; Carnegie Mellon University, USA; University of Southern California, USA)
Article Search
No Distributed Quantum Advantage for Approximate Graph Coloring
Xavier Coiteux-Roy
,
Francesco d'Amore , Rishikesh Gajjala
, Fabian Kuhn
, François Le Gall
, Henrik Lievonen
,
Augusto Modanese , Marc-Olivier Renou
, Gustav Schmid
, and Jukka Suomela
(TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Aalto University, Finland; Bocconi University, Italy; Indian Institute of Science, India; University of Freiburg, Freiburg, Germany; Nagoya University, Nagoya, Japan; Inria, France; Université Paris-Saclay, France; Institut Polytechnique de Paris, France)
Article Search
Packing Even Directed Circuits Quarter-Integrally
Maximilian Gorsky
, Ken-ichi Kawarabayashi
, Stephan Kreutzer
, and Sebastian Wiederrecht
(TU Berlin, Berlin, Germany; National Institute of Informatics, Tokyo, Japan; University of Tokyo, Tokyo, Japan; Institute for Basic Science, South Korea)
Preprint
Sparsifying Generalized Linear Models
Arun Jambulapati
, James R. Lee
, Yang P. Liu
, and Aaron Sidford
(Simons Institute for the Theory of Computing, Berkeley, USA; University of Washington, USA; Institute for Advanced Study, Princeton, USA; Stanford University, USA)
Preprint
Video
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud
, Nick Fischer
, Zander Kelley
, Shachar Lovett
, and Raghu Meka
(Weizmann Institute of Science, Israel; University of Illinois, Urbana-Champaign, USA; University of California, San Diego, USA; University of California, Los Angeles, USA)
Article Search
Learning Shallow Quantum Circuits
Hsin-Yuan Huang , Yunchao Liu
, Michael Broughton
, Isaac Kim
, Anurag Anshu
, Zeph Landau
, and Jarrod R. McClean
(California Institute of Technology, USA; Google Quantum AI, USA; University of California, Berkeley, USA; University of California, Davis, USA; Harvard University, USA)
Article Search
Influences in Mixing Measures
Frederic Koehler
, Noam Lifshitz
, Dor Minzer
, and Elchanan Mossel
(Stanford University, USA; Hebrew University of Jerusalem, Israel; Massachusetts Institute of Technology, USA)
Article Search
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow
Li Chen
, Rasmus Kyng
, Yang P. Liu
, Simon Meierhans
, and Maximilian Probst Gutenberg
(Carnegie Mellon University, USA; ETH Zurich, Switzerland; Institute for Advanced Study, Princeton, USA)
Article Search
Understanding the Cluster Linear Program for Correlation Clustering
Nairen Cao , Vincent Cohen-Addad
, Euiwoong Lee
,
Shi Li , Alantha Newman
, and Lukas Vogl
(Boston College, USA; Google Research, France; University of Michigan, USA; Nanjing University, China; CNRS - Université Grenoble Alpes, France; EPFL, Lausanne, Switzerland)
Article Search
Info
Nonlocality under Computational Assumptions
Grzegorz Gluch
, Khashayar Barooti
, Alexandru Gheorghiu
, and Marc-Olivier Renou
(EPFL, Lausanne, Switzerland; Aztec Labs, United Kingdom; Chalmers University of Technology, Sweden; Inria - Université Paris-Saclay - CPHT - École Polytechnique - Institut Polytechnique de Paris, France)
Preprint
On the Power of Homogeneous Algebraic Formulas
Hervé Fournier, Nutan Limaye
, Srikanth Srinivasan
, and Sébastien Tavenas
(IMJ-PRG - Université Paris Cité, France; IT-Universitetet, Copenhagen, Denmark; University of Copenhagen, Copenhagen, Denmark; Université Savoie Mont Blanc - CNRS - LAMA, France)
Article Search
Batch Proofs Are Statistically Hiding
Nir Bitansky
, Chethan Kamath
, Omer Paneth
, Ron D. Rothblum
, and Prashant Nalini Vasudevan
(Tel Aviv University, Israel; IIT Bombay, India; Technion, Israel; National University of Singapore, Singapore)
Article Search
proc time: 0.48