default search action
63rd FOCS 2022: Denver, CO, USA
- 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022. IEEE 2022, ISBN 978-1-6654-5519-0
- Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
:
Binary Codes with Resilience Beyond 1/4 via Interaction. 1-12 - Ronen Shaltiel, Jad Silbak:
Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits. 13-23 - Gil Cohen, Tal Yankovitz:
Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring. 24-35 - Venkatesan Guruswami, Jonathan Mosheiff:
Punctured Low-Bias Codes Behave Like Random Linear Codes. 36-45 - Jiayu Zhang:
Classical Verification of Quantum Computations in Linear Time. 46-57 - Alexander Meiburg:
Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography. 58-68 - Takashi Yamakawa, Mark Zhandry:
Verifiable Quantum Advantage without Structure. 69-74 - Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan:
Properly learning monotone functions via local correction. 75-86 - Deanna Needell, William Swartworth, David P. Woodruff:
Testing Positive Semidefiniteness Using Linear Measurements. 87-97 - Tali Kaufman, Dor Minzer:
Improved Optimal Testing Results from Global Hypercontractivity. 98-109 - Yuansi Chen, Ronen Eldan:
Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract). 110-122 - Nima Anari, Yang P. Liu
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence. 123-134 - Jeongwan Haah, Robin Kothari
Optimal learning of quantum Hamiltonians from high-temperature Gibbs states. 135-146 - Kun He, Chunyang Wang, Yitong Yin:
Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time. 147-158 - Argyrios Deligkas
Pure-Circuit: Strong Inapproximability for PPAD. 159-170 - Bo Peng, Zhihao Gavin Tang:
Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design. 171-178 - Yaonan Jin, Pinyan Lu
First Price Auction is 1 - 1 /e2 Efficient. 179-187 - Nashlen Govindasamy, Tuomas Hakoniemi
Simple Hard Instances for Low-Depth Algebraic Proofs. 188-199 - Pranjal Dutta
Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits. 200-211 - Rafael Oliveira, Akash Kumar Sengupta:
Radical Sylvester-Gallai Theorem for Cubics. 212-220 - Vishwas Bhargava
Fast Multivariate Multipoint Evaluation Over All Finite Fields. 221-232 - Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao
Solving SDP Faster: A Robust IPM Framework and Efficient Implementation. 233-244 - Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford:
Improved Lower Bounds for Submodular Function Minimization. 245-254 - Adam Brown, Aditi Laddha, Madhusudhan Pittu, Mohit Singh, Prasad Tetali:
Determinant Maximization via Matroid Intersection Algorithms. 255-266 - Xavier Allamigeon, Daniel Dadush, Georg Loho
Interior point methods are not worse than Simplex. 267-277 - Qingyun Chen, Bundit Laekhanukit, Chao Liao, Yuhao Zhang:
Survivable Network Design Revisited: Group-Connectivity. 278-289 - Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams, Nicole Wein:
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles. 290-300 - Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee
Fitting Metrics and Ultrametrics with Minimum Disagreements. 301-311 - Brice Huang, Mark Sellke
Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses. 312-322 - Ahmed El Alaoui, Andrea Montanari, Mark Sellke
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization. 323-334 - Joao Basso, David Gamarnik, Song Mei, Leo Zhou
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. 335-343 - Charlie Carlson, Ewan Davies
Algorithms for the ferromagnetic Potts model on expanders. 344-355 - Robert Andrews:
On Matrix Multiplication and Polynomial Identity Testing. 356-365 - Tsz Chiu Kwok, Lap Chi Lau, Kam Chuen Tung
Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues. 366-377 - Fernando Granha Jeronimo, Tushant Mittal
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification. 378-388 - Michael Kapralov
Motif Cut Sparsifiers. 389-398 - Harm Derksen, Emanuele Viola:
Fooling polynomials using invariant theory*. 399-406 - Rasmus Kyng, Simon Meierhans, Maximilian Probst
Derandomizing Directed Random Walks in Almost-Linear Time. 407-418 - Manik Dhar, Zeev Dvir:
Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds. 419-428 - Lijie Chen, Ron D. Rothblum, Roei Tell:
Unstructured Hardness to Average-Case Randomness. 429-437 - Mohsen Ghaffari:
Local Computation of Maximal Independent Set. 438-449 - Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer
Streaming Facility Location in High Dimension via Geometric Hashing. 450-461 - Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer
The Power of Uniform Sampling for Coresets. 462-473 - Yu Chen, Sanjeev Khanna, Huan Li:
On Weighted Graph Sparsification by Linear Sketching. 474-485 - Ashish Chiplunkar, John Kallaugher, Michael Kapralov
Factorial Lower Bounds for (Almost) Random Order Streams. 486-497 - John Kallaugher, Ojas Parekh
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut. 498-506 - Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay
Cut Query Algorithms with Star Contraction. 507-518 - Xi Chen, Christos H. Papadimitriou, Binghui Peng:
Memory Bounds for Continual Learning. 519-530 - Mina Dalirrooyfard, Virginia Vassilevska Williams:
Induced Cycles and Paths Are Harder Than You Think. 531-542 - Shuichi Hirahara, Nobutaka Shimizu
Hardness Self-Amplification from Feasible Hard-Core Sets. 543-554 - Marvin Künnemann:
A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D. 555-566 - Ludovic Stephan, Yizhe Zhu:
Sparse random hypergraphs: Non-backtracking spectra and community detection. 567-575 - David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu:
Algorithms and Barriers in the Symmetric Binary Perceptron Model. 576-587 - Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang:
Optimal mixing for two-state anti-ferromagnetic spin systems. 588-599 - Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen:
Negative-Weight Single-Source Shortest Paths in Near-linear Time. 600-611 - Li Chen, Rasmus Kyng, Yang P. Liu
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. 612-623 - Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre:
Randomised Composition and Small-Bias Minimax. 624-635 - Jinyoung Park, Huy Tuan Pham:
A Proof of the Kahn-Kalai Conjecture. 636-639 - Hanlin Ren
On the Range Avoidance Problem for Circuits. 640-650 - Vincent Cohen-Addad, Euiwoong Lee
Correlation Clustering with Sherali-Adams. 651-661 - Max Hopkins, Ting-Chun Lin:
Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares. 662-673 - Elazar Goldenberg, Tomasz Kociumaka
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. 674-685 - Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance. 686-697 - Panagiotis Charalampopoulos
Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices. 698-707 - Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein:
Estimating the Longest Increasing Subsequence in Nearly Optimal Time. 708-719 - Soheil Behnezhad, Moses Charikar
Almost 3-Approximate Correlation Clustering in Constant Rounds. 720-731 - David P. Woodruff, Taisuke Yasuda
High-Dimensional Geometric Streaming in Polynomial Space. 732-743 - Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda
Active Linear Regression for ℓp Norms and Beyond. 744-753 - Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, Shangdi Yu
Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs. 754-765 - Shimon Kogan, Merav Parter:
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets. 766-777 - Greg Bodwin, Gary Hoppenworth:
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product. 778-788 - Thatchaphol Saranurak
Deterministic Small Vertex Connectivity in Almost Linear Time. 789-800 - Nikhil Bansal, William Kuszmaul:
Balanced Allocations: The Heavily Loaded Case with Deletions. 801-812 - Namiko Matsumoto, Arya Mazumdar:
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing. 813-822 - Allen Liu, Ankur Moitra:
Minimax Rates for Robust Community Detection. 823-831 - Anna R. Karlin, Nathan Klein
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. 832-843 - Tony Metger, Omar Fawzi, David Sutter
Generalised entropy accumulation. 844-850 - Alex Lombardi, Fermi Ma, Nicholas Spooner:
Post-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably. 851-859 - Christian Ikenmeyer, Igor Pak:
What is in #P and what is not? 860-871 - Anthony Leverrier, Gilles Zémor
Quantum Tanner codes. 872-883 - Amir Abboud, Robert Krauthgamer
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time. 884-895 - Shiri Chechik, Tianyi Zhang:
Constant Approximation of Min-Distances in Near-Linear Time. 896-906 - Virginia Vassilevska Williams, Eyob Woldeghebriel, Yinzhan Xu:
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure. 907-918 - Michael Anastos:
Solving the Hamilton cycle problem fast on average. 919-930 - Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan, Or Zamir:
Planting Undetectable Backdoors in Machine Learning Models : [Extended Abstract]. 931-942 - Nataly Brukhim, Daniel Carmon, Irit Dinur
A Characterization of Multiclass Learnability. 943-955 - Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari, Jeff Xu:
Polynomial-Time Power-Sum Decomposition of Polynomials. 956-967 - Shuichi Hirahara:
NP-Hardness of Learning Programs and Partial MCSP. 968-979 - Michael A. Bender, Alex Conway, Martin Farach-Colton, Hanna Komlós
Online List Labeling: Breaking the log2n Barrier. 980-990 - William Kuszmaul:
A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits. 991-1001 - Yaowei Long, Thatchaphol Saranurak
Near-Optimal Deterministic Vertex-Failure Connectivity Oracles. 1002-1010 - Jan van den Brand
Fast Deterministic Fully Dynamic Distance Approximation. 1011-1022 - Abhishek Jain, Zhengzhong Jin:
Indistinguishability Obfuscation via Mathematical Proofs of Equivalence. 1023-1034 - Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji, Hai H. Nguyen:
Geometry of Secure Two-party Computation. 1035-1044 - Omer Paneth, Rafael Pass
Incrementally Verifiable Computation via Rate-1 Batch Arguments. 1045-1056 - Lalita Devadas, Rishab Goyal, Yael Kalai, Vinod Vaikuntanathan:
Rate-1 Non-Interactive Arguments for Batch-NP and Applications. 1057-1068 - Dimitrios M. Thilikos, Sebastian Wiederrecht
Killing a vortex. 1069-1080 - Arnold Filtser, Hung Le:
Low Treewidth Embeddings of Planar and Minor-Free Metrics. 1081-1092 - Nikhil Kumar:
An Approximate Generalization of the Okamura-Seymour Theorem. 1093-1101 - Sébastien Bubeck, Christian Coester
Shortest Paths without a Map, but with an Entropic Regularizer. 1102-1113 - Václav Rozhon, Michael Elkin, Christoph Grunau
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. 1114-1121 - Giuseppe Antonio Di Luna, Giovanni Viglietta:
Computing in Anonymous Dynamic Networks Is Linear. 1122-1133 - Hamed Hatami, Pooya Hatami
The Implicit Graph Conjecture is False. 1134-1137 - Johan Håstad, Kilian Risse:
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited. 1138-1149 - Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao:
Separations in Proof Complexity and TFNP. 1150-1161 - Aparna Gupte, Neekon Vafa
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures. 1162-1173 - Joakim Blikstad, Jan van den Brand
Nearly Optimal Communication and Query Complexity of Bipartite Matching. 1174-1185 - Huacheng Yu:
Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract). 1186-1192 - Sepehr Assadi, Gillat Kol, Zhijun Zhang
Rounds vs Communication Tradeoffs for Maximal Independent Sets. 1193-1204 - Sitan Chen, Jerry Li, Brice Huang, Allen Liu:
Tight Bounds for Quantum State Certification with Incoherent Measurements. 1205-1213
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 2024-12-17 20:47 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: