default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID54th STOC 2022: Rome, Italy
- Stefano Leonardi, Anupam Gupta:
STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022. ACM 2022, ISBN 978-1-4503-9264-8
Session 1A
- Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen:
Nonlocal games, compression theorems, and the arithmetical hierarchy. 1-11 - Anurag Anshu, Itai Arad, David Gosset:
An area law for 2d frustration-free spin systems. 12-18 - Sevag Gharibian, François Le Gall:
Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture. 19-32 - Arjan Cornelissen, Yassine Hamoudi
, Sofiène Jerbi:
Near-optimal Quantum algorithms for multivariate mean estimation. 33-43 - Anurag Anshu, Zeph Landau, Yunchao Liu:
Distributed Quantum inner product estimation. 44-51
Session 1B
- Nikhil Bansal, Ohad N. Feldheim:
The power of two choices in graphical allocation. 52-63 - George Giakkoupis:
Expanders via local edge flips in quasilinear time. 64-76 - Zhihao Gavin Tang, Jinzhao Wu, Hongxun Wu:
(Fractional) online stochastic matching via fine-grained offline statistics. 77-90 - Zhiyi Huang, Xinkai Shu, Shuyi Yan:
The power of multiple choices in online stochastic matching. 91-103 - Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, Jakub Tarnawski:
Online edge coloring via tree recurrences and correlation decay. 104-116
Session 1C
- Andreas Björklund, Thore Husfeldt, Petteri Kaski:
The shortest even cycle problem is tractable. 117-130 - Zhiyang He, Jason Li:
Breaking the nk barrier for minimum k-cut on simple graphs. 131-136 - Ruoxu Cen, Jason Li, Debmalya Panigrahi:
Edge connectivity augmentation in near-linear time. 137-150 - Seth Pettie, Thatchaphol Saranurak, Longhui Yin:
Optimal vertex connectivity oracles. 151-161 - Sam Coy, Artur Czumaj:
Deterministic massively parallel connectivity. 162-175
Session 2A
- Tom Gur, Noam Lifshitz, Siqi Liu:
Hypercontractivity on high dimensional expanders. 176-184 - Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett:
Hypercontractivity on high dimensional expanders. 185-194 - Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, Nitin Saurabh:
Approximate polymorphisms. 195-202 - Alexandros Eskenazis, Paata Ivanisvili:
Learning low-degree functions from a logarithmic number of random queries. 203-207 - Srinivasan Arunachalam, Penghui Yao:
Positive spectrahedra: invariance principles and pseudorandom generators. 208-221
Session 2B
- Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten:
New streaming algorithms for high dimensional EMD and MST. 222-233 - Sepehr Assadi, Pankaj Kumar, Parth Mittal:
Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring. 234-247 - Manuela Fischer, Slobodan Mitrovic, Jara Uitto:
Deterministic (1+ε)-approximate maximum matching with poly(1/ε) passes in the semi-streaming model and beyond. 248-260 - Sepehr Assadi, Andrew Chen, Glenn Sun:
Deterministic graph coloring in the streaming model. 261-274 - Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy:
Linear space streaming lower bounds for approximating CSPs. 275-288
Session 2C
- Fabrizio Grandoni, Tobias Mömke, Andreas Wiese:
A PTAS for unsplittable flow on a path. 289-302 - Julia Chuzhoy, Zihan Tan:
A subpolynomial approximation algorithm for graph crossing number in low-degree graphs. 303-316 - Matthias Englert, Nicolaos Matsakis, Pavel Veselý:
Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios. 317-330 - Nikhil Bansal, Lars Rohwedder, Ola Svensson:
Flow time scheduling and prefix Beck-Fiala. 331-342 - Vincent Cohen-Addad:
Bypassing the surface embedding: approximation schemes for network design in minor-free graphs. 343-356
Award Papers Session I: Best Papers
- Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes:
Locally testable codes with constant rate, distance, and locality. 357-374 - Pavel Panteleev, Gleb Kalachev:
Asymptotically good Quantum and locally testable classical LDPC codes. 375-388
Session 3A
- Robert Andrews, Michael A. Forbes:
Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals. 389-402 - Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, Chandra Kanta Mohapatra:
Fast, algebraic multivariate multipoint evaluation in small characteristic and applications. 403-415 - Sébastien Tavenas, Nutan Limaye, Srikanth Srinivasan:
Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. 416-425 - Amitay Kamber, Tali Kaufman:
Combinatorics via closed orbits: number theoretic Ramanujan graphs are not unique neighbor expanders. 426-435 - Andrei A. Bulatov, Akbar Rafiey:
On the complexity of CSP-based ideal membership problems. 436-449
Session 3B
- Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, Tigran Tonoyan:
Near-optimal distributed degree+1 coloring. 450-463 - Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti:
Distributed ∆-coloring plays hide-and-seek. 464-477 - Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li:
Undirected (1+ε)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms. 478-487 - Mohammad Taghi Hajiaghayi, Dariusz R. Kowalski, Jan Olkowski:
Improved communication complexity of fault-tolerant consensus. 488-501 - Shang-En Huang, Seth Pettie, Leqi Zhu:
Byzantine agreement in polynomial time with near-optimal resilience. 502-514
Session 3C
- Xavier Allamigeon, Stéphane Gaubert, Nicolas Vandame:
No self-concordant barrier interior point method is strongly polynomial. 515-528 - Arun Jambulapati, Yang P. Liu, Aaron Sidford:
Improved iteration complexities for overconstrained p-norm regression. 529-542 - Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, Aaron Sidford:
Faster maxflow via improved dynamic spectral vertex sparsifiers. 543-556 - Richard Peng, Zhuoqing Song:
Sparsified block elimination for directed laplacians. 557-567 - Zipei Nie:
Matrix anti-concentration inequalities with applications. 568-581
Session 4A
- Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena:
Circuits resilient to short-circuit errors. 582-594 - Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz:
Explicit binary tree codes with sub-logarithmic size alphabet. 595-608 - Meghal Gupta, Yael Tauman Kalai, Rachel Yun Zhang:
Interactive error correcting codes over binary erasure channels resilient to > ½ adversarial corruption. 609-622 - Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan:
The query complexity of certification. 623-636
Session 4B
- Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty:
Matrix discrepancy from Quantum communication. 637-648 - Daniel Dadush, Haotian Jiang, Victor Reis:
A new framework for matrix discrepancy: partial coloring bounds via mirror descent. 649-658 - Yeshwanth Cherapanamjeri, Jelani Nelson:
Uniform approximations for Randomized Hadamard Transforms with applications. 659-671 - Siqi Liu, Sidhanth Mohanty, Tselil Schramm, Elizabeth Yang:
Testing thresholds for high-dimensional sparse random geometric graphs. 672-677 - Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. 678-689
Session 4C
- Shahar Dobzinski, Shiri Ron, Jan Vondrák:
On the hardness of dominant strategy mechanism design. 690-703 - Yang Cai, Argyris Oikonomou, Mingfei Zhao:
Computing simple mechanisms: Lift-and-round over marginal reduced forms. 704-717 - Yuan Deng, Jieming Mao, Balasubramanian Sivan, Kangning Wang:
Approximately efficient bilateral trade. 718-721 - Shuchi Chawla, Rojin Rezvan, Yifeng Teng, Christos Tzamos:
Pricing ordered items. 722-735 - Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, Tuomas Sandholm:
Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. 736-749
Session 5A
- Dorit Aharonov, Sandy Irani:
Hamiltonian complexity in the thermodynamic limit. 750-763 - James D. Watson, Toby S. Cubitt:
Computational complexity of the ground state energy density problem. 764-775 - Matthew B. Hastings, Ryan O'Donnell:
Optimizing strongly interacting fermionic Hamiltonians. 776-789 - Omri Shmueli:
Public-key Quantum money with a classical bank. 790-803 - Zvika Brakerski, Henry Yuen:
Quantum garbled circuits. 804-817
Session 5B
- Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell:
Reproducibility in learning. 818-831 - Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau:
Kalman filtering with adversarial corruptions. 832-845 - Constantinos Daskalakis, Noah Golowich:
Fast rates for nonparametric online learning: from realizability to learning in games. 846-859 - Emmanuel Abbe, Shuangping Li, Allan Sly:
Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster. 860-873 - Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis:
Learning general halfspaces with general Massart noise under the Gaussian distribution. 874-885
Session 5C
- Fedor V. Fomin, Tuukka Korhonen:
Fast FPT-approximation of branchwidth. 886-899 - Bart M. P. Jansen, Michal Wlodarczyk:
Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion. 900-913 - Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor. 914-923 - Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Torunczyk:
Twin-width IV: ordered graphs and matrices. 924-937 - Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Directed flow-augmentation. 938-947
Award Papers Session II: Best Student Papers
- Meghal Gupta, Rachel Yun Zhang:
The optimal error resilience of interactive communication over binary channels. 948-961 - Zhiyuan Fan, Jiatu Li, Tianqi Yang:
The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity. 962-975
Session 6A
- Amey Bhangale, Subhash Khot, Dor Minzer:
On approximability of satisfiable k-CSPs: I. 976-988 - Euiwoong Lee, Suprovat Ghoshal:
A characterization of approximability for biased CSPs. 989-997 - Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan:
Parallel repetition for all 3-player games over binary alphabet. 998-1009 - Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos:
Constant inapproximability for PPA. 1010-1023 - Andrei A. Bulatov, Amirhossein Kazeminia:
Complexity classification of counting graph homomorphisms modulo a prime number. 1024-1037
Session 6B
- Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn:
Towards optimal lower bounds for k-median and k-means coresets. 1038-1051 - Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra, Allen Xiao:
Deterministic, near-linear ε-approximation algorithm for geometric bipartite matching. 1052-1065 - Arnold Filtser, Hung Le:
Locality-sensitive orderings and applications to reliable spanners. 1066-1079 - Merav Parter:
Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel. 1080-1092 - Ran Duan, Hanlin Ren:
Maintaining exact distances under multiple edge failures. 1093-1101
Session 6C
- Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos:
Almost-optimal sublinear-time edit distance in the low distance regime. 1102-1115 - Jakub Tetek, Mikkel Thorup:
Edge sampling and graph parameter estimation via vertex neighborhood accesses. 1116-1129 - Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff:
Low-rank approximation with 1/ε1/3 matrix-vector products. 1130-1143 - Vladimir Braverman, Aditya Krishnan, Christopher Musco:
Sublinear time spectral density estimation. 1144-1157 - Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou:
Memory bounds for the experts problem. 1158-1171
Session 7A
- Philipp Hieronymi, Christian Schulz:
A strong version of Cobham's theorem. 1172-1179 - Jiatu Li, Tianqi Yang:
3.1n - o(n) circuit lower bounds for explicit functions. 1180-1193 - Alexander A. Sherstov:
The approximate degree of DNF and CNF formulas. 1194-1207 - Tal Herman, Guy N. Rothblum:
Verifying the unseen: interactive proofs for label-invariant distribution properties. 1208-1219 - Nathaniel Harms, Sebastian Wild, Viktor Zamaraev:
Randomized communication and implicit graph representations. 1220-1233
Session 7B
- Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala:
Robustly learning mixtures of k arbitrary Gaussians. 1234-1247 - Allen Liu, Jerry Li:
Clustering mixtures with almost optimal separation in polynomial time. 1248-1261 - Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian:
Clustering mixture models in almost-linear time via list-decodable mean estimation. 1262-1275 - Misha Ivkov, Pravesh K. Kothari:
List-decodable covariance estimation. 1276-1283
Session 7C
- Michael A. Bender, Martin Farach-Colton, John Kuszmaul, William Kuszmaul, Mingmou Liu:
On the optimal time/space tradeoff for hash tables. 1284-1297 - Ioana Oriana Bercea, Guy Even:
An extendable data structure for incremental stable perfect hashing. 1298-1310 - Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan:
Almost-linear ε-emulators for planar graphs. 1311-1324 - Bernhard Haeupler, Harald Räcke, Mohsen Ghaffari:
Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. 1325-1338 - Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Kleinberg, Rachit Agarwal:
Optimal oblivious reconfigurable networks. 1339-1352
Session 8A
- Noga Ron-Zewi, Ron D. Rothblum:
Proving as fast as computing: succinct arguments with constant prover overhead. 1353-1363 - Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, Sruthi Sekar:
Rate one-third non-malleable codes. 1364-1377 - Andrea Coladangelo, Shafi Goldwasser, Umesh V. Vazirani:
Deniable encryption in a Quantum world. 1378-1391 - Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia:
On the complexity of two-party differential privacy. 1392-1405 - Samuel B. Hopkins, Gautam Kamath, Mahbod Majid:
Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. 1406-1417
Session 8B
- Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, Thuy-Duong Vuong:
Entropic independence: optimal mixing of down-up random walks. 1418-1430 - Hongyang Liu, Yitong Yin:
Simple parallel algorithms for single-site dynamics. 1431-1444 - Reza Gheissari, Alistair Sinclair:
Low-temperature Ising dynamics with random initializations. 1445-1458 - Charlie Carlson, Ewan Davies, Alexandra Kolla, Will Perkins:
Computational thresholds for the fixed-magnetization Ising model. 1459-1472 - Vishesh Jain, Will Perkins, Ashwin Sah, Mehtaab Sawhney:
Approximate counting and sampling via local central limit theorems. 1473-1486
Session 8C
- Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir:
Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond. 1487-1500 - Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu:
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV. 1501-1514 - Ce Jin, Yinzhan Xu:
Tight dynamic problem lower bounds from generalized BMM and OMv. 1515-1528 - Shucheng Chi, Ran Duan, Tianle Xie, Tianyi Zhang:
Faster min-plus product for monotone instances. 1529-1542 - Jacob Focke, Marc Roth:
Counting small induced subgraphs with hereditary properties. 1543-1551
Session 9A
- Peter Dixon, Aduri Pavan, Jason Vander Woude, N. V. Vinodchandran:
Pseudodeterminism: promises and lowerbounds. 1552-1565 - Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar:
Worst-case to average-case reductions via additive combinatorics. 1566-1574 - Rahul Ilango, Hanlin Ren, Rahul Santhanam:
Robustness of average-case meta-complexity via pseudorandomness. 1575-1583 - Eshan Chattopadhyay, Jyun-Jie Liao:
Extractors for sum of two sources. 1584-1597
Session 9B
- Fabrizio Grandoni, Afrouz Jabal Ameli, Vera Traub:
Breaching the 2-approximation barrier for the forest augmentation problem. 1598-1611 - Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang:
An improved approximation algorithm for the minimum k-edge connected multi-subgraph problem. 1612-1620 - Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan:
Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets. 1621-1628 - Konstantin Makarychev, Liren Shan:
Explainable k-means: don't be greedy, plant bigger trees! 1629-1642
Session 9C
- Adam Karczmarz, Anish Mukherjee, Piotr Sankowski:
Subquadratic dynamic path reporting in directed graphs against an adaptive adversary. 1643-1656 - Dominik Kempa, Tomasz Kociumaka:
Dynamic suffix array with polylogarithmic queries and updates. 1657-1670 - Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, Uri Stemmer:
Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. 1671-1684 - Xi Chen, Binghui Peng:
On the complexity of dynamic submodular maximization. 1685-1698
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-05 22:33 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
