default search action
64th FOCS 2023: Santa Cruz, CA, USA
- 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023. IEEE 2023, ISBN 979-8-3503-1894-4
- Jonas Conneryd, Susanna F. de Rezende
, Jakob Nordström
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. 1-11 - Susanna F. de Rezende
Clique Is Hard on Average for Unary Sherali-Adams. 12-25 - Suprovat Ghoshal, Euiwoong Lee
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs. 26-36 - Johan Håstad:
On small-depth Frege proofs for PHP. 37-49 - Nathan Klein
Thin Trees for Laminar Families. 50-59 - Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D. Ellis Hershkowitz, Rajmohan Rajaraman:
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree. 60-76 - Hung Le, Shay Solomon, Cuong Than:
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier. 77-97 - Alexandr Andoni, Hengjie Zhang:
Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications. 98-112 - Alexandros Hollender, Aviad Rubinstein:
Envy-Free Cake-Cutting for Four Agents. 113-122 - Neil Olver, Leon Sering
Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time. 123-133 - Yang Cai, Ziyun Chen, Jinzhao Wu:
Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders. 134-147 - Alon Eden, Michal Feldman, Kira Goldner
Constant Approximation for Private Interdependent Valuations. 148-163 - Zeyu Guo, Zihan Zhang
Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets. 164-176 - Emmanuel Abbe, Colin Sandon:
A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels. 177-193 - Silas Richelson, Sourya Roy:
Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal Binary Codes. 194-205 - Dor Minzer, Kai Zhe Zheng:
Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries. 206-233 - Joshua Brakensiek, Neng Huang
Separating MAX 2-AND, MAX DI-CUT and MAX CUT. 234-252 - Vaggos Chatziafratis, Konstantin Makarychev:
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant. 253-284 - Bingkai Lin
Improved Hardness of Approximating k-Clique under ETH. 285-306 - Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar:
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. 307-327 - Arturo Acuaviva, Visu Makam, Harold Nieuwboer, David Pérez-García, Friedrich Sittner, Michael Walter, Freek Witteveen:
The minimal canonical form of a tensor network. 328-362 - Jeongwan Haah
Query-optimal estimation of unitary channels in diamond distance. 363-390 - Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke:
When Does Adaptivity Help for Quantum State Learning? 391-404 - Ryan Babbush, Dominic W. Berry
Exponential quantum speedup in simulating coupled classical oscillators*. 405-414 - Yao-Ching Hsieh, Huijia Lin, Ji Luo
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices. 415-434 - Valerio Cini, Hoeteck Wee:
ABE for Circuits with poly (λ) -sized Keys from LWE. 435-446 - Shuichi Hirahara, Mikito Nanashima:
Learning in Pessiland via Inductive Inference. 447-457 - Marshall Ball
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement. 458-483 - Ran Duan, Jiayi Mao, Xinkai Shu
A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs. 484-492 - Jan van den Brand
Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques. 493-502 - Jan van den Brand
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. 503-514 - Karl Bringmann, Alejandro Cassis, Nick Fischer:
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! 515-538 - Benny Applebaum, Oded Nir:
Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography. 539-555 - Eric Ruzomberka, Homa Nikbakht, Christopher G. Brinton, H. Vincent Poor:
On Pseudolinear Codes for Correcting Adversarial Errors. 556-567 - Xiao Liang, Omkant Pandey, Takashi Yamakawa:
A New Approach to Post-Quantum Non-Malleability. 568-579 - Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar, Pasin Manurangsi:
Towards Separating Computational and Statistical Differential Privacy. 580-599 - Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi:
Bridge Girth: A Unifying Notion in Network Design. 600-648 - Michal Wlodarczyk, Meirav Zehavi:
Planar Disjoint Paths, Treewidth, and Kernels. 649-662 - Szymon Torunczyk:
Flip-width: Cops and Robber on dense graphs. 663-700 - Greg Bodwin, Gary Hoppenworth:
Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier. 701-720 - Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu:
Fourier Growth of Communication Protocols for XOR Functions. 721-732 - Rahul Ilango:
SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle. 733-742 - Tal Herman, Guy N. Rothblum:
Doubley-Efficient Interactive Proofs for Distribution Properties. 743-751 - Gal Arnon
IOPs with Inverse Polynomial Soundness Error. 752-761 - Soh Kumabe, Yuichi Yoshida:
Lipschitz Continuous Algorithms for Graph Problems. 762-797 - Martin Grohe, Moritz Lichter, Daniel Neuen, Pascal Schweitzer
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements. 798-809 - Zongchen Chen, Kuikui Liu, Nitya Mani, Ankur Moitra:
Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications. 810-845 - AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan:
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs. 846-854 - Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy:
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. 855-870 - Shachar Lovett, Jiapeng Zhang:
Streaming Lower Bounds and Asymmetric Set-Disjointness. 871-882 - Vincent Cohen-Addad, David P. Woodruff, Samson Zhou:
Streaming Euclidean k-median and k-means with o(log n) Space. 883-908 - Sepehr Assadi, Janani Sundaresan:
Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings. 909-932 - Zander Kelley, Raghu Meka:
Strong Bounds for 3-Progressions. 933-973 - Victor Reis, Thomas Rothvoss:
The Subspace Flatness Conjecture and Faster Integer Programming. 974-988 - Edward Pyne, Ran Raz, Wei Zhan:
Certified Hardness vs. Randomness for Log-Space. 989-1007 - Lijie Chen, Roei Tell, Ryan Williams
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. 1008-1047 - Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Top-Down Lower Bounds for Depth-Four Circuits. 1048-1055 - Or Meir:
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition. 1056-1081 - Vincent Cohen-Addad, Euiwoong Lee
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. 1082-1104 - Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn:
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. 1105-1130 - Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson, Rachel Yuan:
The Price of Explainability for Clustering. 1131-1148 - Jane Lange, Arsen Vasilyan:
Agnostic proper learning of monotone functions: beyond the black-box correction barrier. 1149-1170 - Binghui Peng, Aviad Rubinstein:
Near Optimal Memory-Regret Tradeoff for Online Learning. 1171-1194 - Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang:
Tight Time-Space Lower Bounds for Constant-Pass Learning. 1195-1202 - Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy:
Optimal PAC Bounds without Uniform Convergence. 1203-1223 - Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, Hongxun Wu:
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. 1224-1239 - Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes
Explicit orthogonal and unitary designs. 1240-1260 - Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren
Polynomial-Time Pseudodeterministic Construction of Primes. 1261-1270 - Xin Li:
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More. 1271-1281 - Arturo Merino, Torsten Mütze:
Traversing combinatorial 0/1-polytopes via optimization. 1282-1291 - Rainie Bozzai, Victor Reis, Thomas Rothvoss:
The Vector Balancing Constant for Zonotopes. 1292-1300 - Emily Fox, Jiashuai Lu:
A deterministic near-linear time approximation scheme for geometric transportation. 1301-1315 - Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan:
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. 1316-1336 - Mark Braverman, Subhash Khot, Dor Minzer:
Parallel Repetition for the GHZ Game: Exponential Decay. 1337-1341 - Anand Natarajan, Tina Zhang:
Bounding the Quantum Value of Compiled Nonlocal Games: From CHSH to BQP Verification. 1342-1348 - Tony Metger, Henry Yuen:
stateQIP = statePSPACE. 1349-1356 - Reilly Browne
Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon. 1357-1365 - Ariel Kulik, Matthias Mnich, Hadas Shachnai:
Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding. 1366-1376 - Fateme Abbasi, Sandip Banerjee
Parameterized Approximation Schemes for Clustering with General Norm Objectives. 1377-1399 - Xi Chen, Binghui Peng:
Memory-Query Tradeoffs for Randomized Convex Optimization. 1400-1413 - Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang:
Quartic Samples Suffice for Fourier Interpolation. 1414-1425 - Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi:
Fast Numerical Multivariate Multipoint Evaluation. 1426-1439 - Ioana O. Bercea
Locally Uniform Hashing. 1440-1470 - Josh Alman, Hengjie Zhang:
Generalizations of Matrix Multiplication can solve the Light Bulb Problem. 1471-1495 - Ofer Grossman, Meghal Gupta, Mark Sellke:
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting. 1496-1504 - Marshall Ball
Extracting Randomness from Samplable Distributions, Revisited. 1505-1514 - Praneeth Kacham, Rasmus Pagh, Mikkel Thorup
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. 1515-1550 - Mohsen Ghaffari, Christoph Grunau, Václav Rozhon:
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence. 1551-1562 - Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time. 1563-1588 - Kasper Green Larsen, Huacheng Yu:
Super-Logarithmic Lower Bounds for Dynamic Graph Problems. 1589-1604 - Shunhua Jiang, Binghui Peng, Omri Weinstein:
The Complexity of Dynamic Least-Squares Regression. 1605-1627 - Tomasz Kociumaka, Anish Mukherjee
Approximating Edit Distance in the Fully Dynamic Model. 1628-1638 - Louis Golowich:
From Grassmannian to Simplicial High-Dimensional Expanders. 1639-1648 - Itay Cohen, Roy Roth, Amnon Ta-Shma:
HDX Condensers. 1649-1664 - Vishesh Jain, Marcus Michelen, Huy Tuan Pham, Thuy-Duong Vuong:
Optimal mixing of the down-up walk on independent sets of a given size. 1665-1681 - Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani:
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates. 1682-1693 - Sayan Bhattacharya, Niv Buchbinder, Roie Levin, Thatchaphol Saranurak
Chasing Positive Bodies. 1694-1714 - Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou
Dynamic "Succincter". 1715-1733 - Tuukka Korhonen
Dynamic treewidth. 1734-1744 - Adam Karczmarz, Piotr Sankowski:
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form. 1745-1756 - Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan:
A strong composition theorem for junta complexity and the boosting of property testers. 1757-1777 - Xi Chen, Shyamal Patel:
New Lower Bounds for Adaptive Tolerant Junta Testing. 1778-1786 - Eric Blais, Cameron Seth:
Testing Graph Properties with the Container Method. 1787-1795 - Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
A d1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids. 1796-1821 - William Kuszmaul:
Strongly History-Independent Storage Allocation: New Upper and Lower Bounds. 1822-1841 - Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries. 1842-1862 - Nick Gravin, Enze Sun, Zhihao Gavin Tang:
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity. 1863-1876 - Dominik Kempa, Tomasz Kociumaka:
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space. 1877-1886 - Johannes Carmesin, Jan Kurkofka
Canonical decompositions of 3-connected graphs. 1887-1920 - Vida Dujmovic, Louis Esperet, Pat Morin, David R. Wood:
Proof of the Clustered Hadwiger Conjecture. 1921-1930 - Ohad Klein:
Slicing all Edges of an n-cube Requires n2/3 Hyperplanes. 1931-1936 - Paul Jungeblut
Directed Acyclic Outerplanar Graphs Have Constant Stack Number. 1937-1952 - Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford:
Sparsifying Sums of Norms. 1953-1962 - Weiming Feng, Heng Guo, Chunyang Wang, Jiaheng Wang, Yitong Yin:
Towards derandomising Markov chain Monte Carlo. 1963-1990 - Xiaoyu Chen, Jingcheng Liu, Yitong Yin:
Uniqueness and Rapid Mixing in the Bipartite Hardcore Model (extended abstract). 1991-2005 - Antonio Blanca, Reza Gheissari:
Sampling from the Potts model at low temperatures via Swendsen-Wang dynamics. 2006-2020 - Hiroshi Hirai, Harold Nieuwboer, Michael Walter:
Interior-point methods on manifolds: theory and applications. 2021-2030 - Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, Kevin Tian:
ReSQueing Parallel and Private Stochastic Convex Optimization. 2031-2058 - Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala:
The Bit Complexity of Efficient Continuous Optimization. 2059-2070 - Andrei Graur, Haotian Jiang, Aaron Sidford:
Sparse Submodular Function Minimization. 2071-2080 - Mehrdad Ghadiri:
On Symmetric Factorizations of Hankel Matrices. 2081-2092 - Ainesh Bakshi, Shyam Narayanan:
Krylov Methods are (nearly) Optimal for Low-Rank Approximation. 2093-2101 - Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian:
Matrix Completion in Almost-Verification Time. 2102-2128 - Ran Duan, Hongxun Wu, Renfei Zhou
Faster Matrix Multiplication via Asymmetric Hashing. 2129-2138 - Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, Shyam Narayanan:
Query lower bounds for log-concave sampling. 2139-2148 - Guy Bresler, Chenghao Guo, Yury Polyanskiy:
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles. 2149-2158 - Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, Shyam Narayanan:
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination. 2159-2168 - Jason M. Altschuler, Sinho Chewi:
Faster high-accuracy log-concave sampling via algorithmic warm starts. 2169-2176 - Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz
Optimal Algorithms for Bounded Weighted Edit Distance. 2177-2187 - Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu:
Faster Algorithms for Text-to-Pattern Hamming Distances. 2188-2203 - Amir Abboud, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time. 2204-2212 - Divesh Aggarwal, Rajendra Kumar:
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms! 2213-2230 - Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than:
Covering Planar Metrics (and Beyond): O(1) Trees Suffice. 2231-2261 - Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk:
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. 2262-2277 - Michael Elkin, Idan Shabat:
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n). 2278-2311 - Jan van den Brand
Deterministic Fully Dynamic SSSP and More. 2312-2321 - Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein:
Local Computation Algorithms for Maximum Matching: New Lower Bounds. 2322-2335 - Merav Parter:
Secure Computation Meets Distributed Universal Optimality. 2336-2368 - Ashwin Sah, Mehtaab Sawhney:
Distribution of the threshold for the symmetric perceptron. 2369-2382 - Caleb Koch, Carmen Strassle, Li-Yang Tan:
Properly learning decision trees with queries is NP-hard. 2383-2407 - He Jia, Pravesh K. Kothari, Santosh S. Vempala:
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. 2408-2429 - Zachary Chase, Shay Moran, Amir Yehudayoff:
Stability and Replicability in Learning. 2430-2439
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-13 19:16 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: