default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID65th FOCS 2024: Chicago, IL, USA
- 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024. IEEE 2024, ISBN 979-8-3315-1674-1
- Max Hopkins, Russell Impagliazzo, Daniel M. Kane, Sihan Liu, Christopher Ye:
Replicability in High Dimensional Statistics. 1-8 - Jiatu Li, Edward Pyne, Roei Tell:
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness. 1-13 - Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani, Irene Muzi:
Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem. 1-20 - Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, Szymon Torunczyk:
First-Order Model Checking on Monadically Stable Graph Classes. 21-30 - Christophe Paul, Evangelos Protopapas
, Dimitrios M. Thilikos, Sebastian Wiederrecht:
Obstructions to Erdös-Pósa Dualities for Minors. 31-52 - Tuukka Korhonen, Michal Pilipczuk, Giannos Stamoulis:
Minor Containment and Disjoint Paths in Almost-Linear Time. 53-61 - Loukas Georgiadis, Giuseppe F. Italiano, Evangelos Kosinas:
Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time. 62-85 - Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Tomohiro Sonobe:
Three-Edge-Coloring Projective Planar Cubic Graphs: A Generalization of the Four Color Theorem. 86-105 - Tolson Bell, Alan M. Frieze:
O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold. 106-119 - Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, David X. Wu:
Fast Mixing in Sparse Random Ising Models. 120-128 - Chunyang Wang, Yitong Yin:
A Sampling Lovász Local Lemma for Large Domain Sizes. 129-150 - Matthew Jenssen, Will Perkins, Aditya Potukuchi, Michael Simkin:
Sampling, Counting, and Large Deviations for Triangle-Free Graphs Near the Critical Density. 151-165 - Jordan Cotler, Semon Rezchikov:
Computational Dynamical Systems. 166-202 - Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, David X. Wu:
Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains. 203-215 - Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, Nikos Parotsidis:
Fully Dynamic k-Clustering with Fast Update Time and Small Recourse. 216-227 - Yang P. Liu:
On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication. 228-243 - Lunjia Hu, Yifan Wu:
Predict to Minimize Swap Regret for All Payoff-Bounded Tasks. 244-263 - Shay Solomon, Amitai Uzrad, Tianyi Zhang:
A Lossless Deamortization for Dynamic Greedy Set Cover. 264-290 - Daniel Hathcock, Billy Jin, Kalen Patton, Sherry Sarkar, Michael Zlatin:
The Online Submodular Assignment Problem. 291-313 - Soheil Behnezhad, Alma Ghafari:
Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs. 314-327 - Rohan Goyal, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar:
Fast List Decoding of Univariate Multiplicity and Folded Reed-Solomon Codes. 328-343 - Louis Golowich, Venkatesan Guruswami:
Decoding Quasi-Cyclic Quantum LDPC Codes. 344-368 - Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima:
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications. 369-378 - Irit Dinur, Ting-Chun Lin, Thomas Vidick:
Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes. 379-385 - Shiri Ron, Clayton Thomas, S. Matthew Weinberg, Qianfan Zhang:
Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier. 386-405 - Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun:
On Pigeonhole Principles and Ramsey in TFNP. 406-428 - Siddharth Iyer, Anup Rao:
An XOR Lemma for Deterministic Communication Complexity. 429-432 - Alexander A. Sherstov, Andrey A. Storozhenko:
The Communication Complexity of Approximating Matrix Rank. 433-462 - Jeongwan Haah, Yunchao Liu, Xinyu Tan:
Efficient Approximate Unitary Designs from Random Pauli Rotations. 463-475 - Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, Fernando G. S. L. Brandão, Patrick Hayden:
Efficient Unitary Designs from Random Sums and Permutations. 476-484 - Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen:
Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries. 485-492 - Robbie King, Tamara Kohler:
Gapped Clique Homology on Weighted Graphs is QMA1-Hard and Contained in QMA. 493-504 - Lijie Chen, Jiatu Li, Igor C. Oliveira:
Reverse Mathematics of Complexity Lower Bounds. 505-527 - Tal Herman, Guy N. Rothblum:
Interactive Proofs for General Distribution Properties. 528-538 - Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay:
Trading Determinism for Noncommutativity in Edmonds' Problem. 539-559 - Dmitriy Zhuk:
∏2P vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem. 560-572 - Erfan Khaniki:
Jump Operators, Interactive Proofs and Proof Complexity Generators. 573-593 - Martín Farach-Colton, Andrew Krapivin, William Kuszmaul:
Optimal Bounds for Open Addressing Without Reordering. 594-605 - Mark Braverman, William Kuszmaul:
Tight Analyses of Ordered and Unordered Linear Probing. 606-635 - Michael A. Bender, William Kuszmaul, Renfei Zhou:
Tight Bounds for Classical Open Addressing. 636-657 - Shyam Narayanan, Václav Rozhon, Jakub Tetek, Mikkel Thorup:
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation. 658-688 - Michal Opler:
An Optimal Algorithm for Sorting Pattern-Avoiding Sequences. 689-699 - Niv Buchbinder, Moran Feldman:
Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint. 700-712 - Nikhil Bansal, Dor Katzelnick, Roy Schwartz:
On Approximating Cutwidth and Pathwidth. 713-729 - Jaroslaw Byrka, Fabrizio Grandoni, Vera Traub:
The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller Than 2. 730-753 - Viktoriia Korchemna, Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan, Jie Xue:
Efficient Approximation of Fractional Hypertree Width. 754-779 - Youming Qiao, Xiaorui Sun:
Canonical Forms for Matrix Tuples in Polynomial Time. 780-789 - Sasank Mouli:
Polynomial Calculus Sizes Over the Boolean and Fourier Bases are Incomparable. 790-796 - Gil Kalai, Noam Lifshitz, Dor Minzer, Tamar Ziegler:
A Dense Model Theorem for the Boolean Slice. 797-805 - Nir Bitansky, Prahladh Harsha, Yuval Ishai, Ron D. Rothblum, David J. Wu:
Dot-Product Proofs and Their Applications. 806-825 - Yotam Dikstein, Irit Dinur, Alexander Lubotzky:
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs. 826-861 - Mitali Bafna, Noam Lifshitz, Dor Minzer:
Constant Degree Direct Product Testers with Small Soundness. 862-869 - Yotam Dikstein, Max Hopkins:
Chernoff Bounds and Reverse Hypercontractivity on HDX. 870-919 - Eric Culf, Hamoon Mousavi, Taro Spirig:
Approximation Algorithms for Noncommutative CSPs. 920-929 - Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra:
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold. 930-948 - Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang, Aaron Potechin:
Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis. 949-958 - Jaroslaw Blasiok, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer:
Semirandom Planted Clique and the Restricted Isometry Property. 959-969 - Ainesh Bakshi, Pravesh K. Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan:
Efficient Certificates of Anti-Concentration Beyond Gaussians. 970-987 - Jane H. Lee, Anay Mehrotra, Manolis Zampetakis:
Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians. 988-1006 - Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein:
Tensor Cumulants for Statistical Inference on Invariant Distributions. 1007-1026 - Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang:
High-Temperature Gibbs States are Unentangled and Efficiently Preparable. 1027-1036 - Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang:
Structure Learning of Hamiltonians from Real-Time Evolution. 1037-1050 - Guang Hao Low, Yuan Su:
Quantum Eigenvalue Processing. 1051-1062 - Thiago Bergamaschi, Chi-Fang Chen, Yunchao Liu:
Quantum Computational Advantage with Constant-Temperature Gibbs Sampling. 1063-1085 - Sitan Chen, Weiyuan Gong, Qi Ye:
Optimal Tradeoffs for Estimating Pauli Observables. 1086-1105 - Atul Singh Arora, Kishor Bharti, Alexandru Cojocaru, Andrea Coladangelo:
A Computational Test of Contextuality and, Even Simpler Proofs of Quantumness. 1106-1125 - Brice Huang:
Capacity Threshold for the Ising Perceptron. 1126-1136 - Meghal Gupta, Mihir Singhal, Hongxun Wu:
Optimal Quantile Estimation: Beyond the Comparison Model. 1137-1158 - Leonid Reyzin:
Proofs of Space with Maximal Hardness. 1159-1177 - Rishabh Batra, Rahul Jain:
Commitments are Equivalent to Statistically-Verifiable One-Way State Generators. 1178-1192 - Tony Metger, Anand Natarajan, Tina Zhang:
Succinct Arguments for QMA from Standard Assumptions via Compiled Nonlocal Games. 1193-1201 - Hsin-Yuan Huang, John Preskill, Mehdi Soleimanifar:
Certifying Almost All Quantum States with Few Single-Qubit Measurements. 1202-1206 - Yevgeniy Dodis, Aayush Jain, Huijia Lin, Ji Luo, Daniel Wichs:
How to Simulate Random Oracles with Auxiliary Input. 1207-1230 - Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiffenhäuser, Sahil Singla:
Online Combinatorial Allocations and Auctions with Few Samples. 1231-1250 - Yaonan Jin, Pinyan Lu:
Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer. 1251-1259 - Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan:
Semi-Bandit Learning for Monotone Stochastic Optimization. 1260-1274 - Nick Gravin, Zhiqi Wang:
On Robustness to k-Wise Independence of Optimal Bayesian Mechanisms. 1275-1293 - Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, Amin Saberi:
Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting. 1294-1331 - Dmitry Chistikov, Wojciech Czerwinski, Filip Mazowiecki, Lukasz Orlikowski, Henry Sinclair-Banks, Karol Wegrzycki:
The Tractability Border of Reachability in Simple Vector Addition Systems with States. 1332-1354 - Mikkel Abrahamsen, Jack Stade:
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares. 1355-1371 - Ryan Williams:
The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds. 1372-1387 - Oliver Korten, Toniann Pitassi:
Strong vs. Weak Range Avoidance and the Linear Ordering Principle. 1388-1407 - Gábor Ivanyos, Euan J. Mendoza, Youming Qiao, Xiaorui Sun, Chuanqi Zhang:
Faster Isomorphism Testing of p-Groups of Frattini Class 2. 1408-1424 - Harm Derksen, Chin Ho Lee, Emanuele Viola:
Boosting Uniformity in Quasirandom Groups: Fast and Simple. 1425-1430 - Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan:
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem. 1431-1450 - Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach:
On the Existence of Seedless Condensers: Exploring the Terrain. 1451-1469 - Gil Cohen, Itay Cohen, Gal Maor:
Tight Bounds for the Zig-Zag Product. 1470-1499 - Jesse Goodman, Xin Li, David Zuckerman:
Improved Condensers for Chor-Goldreich Sources. 1513-1549 - Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck:
Improved Distance (Sensitivity) Oracles with Subquadratic Space. 1550-1558 - Yuval Filmus, Hamed Hatami, Kaave Hosseini, Esty Kelman:
Sparse Graph Counting and Kelley-Meka Bounds for Binary Systems. 1559-1578 - Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, Tianyi Zhang:
Towards Instance-Optimal Euclidean Spanners. 1579-1609 - Friedrich Eisenbrand, Lars Rohwedder, Karol Wegrzycki:
Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems. 1610-1620 - Dmitriy Kunisky, Xifan Yu:
Computational Hardness of Detecting Graph Lifts and Certifying Lift-Monotone Properties of Random Regular Graphs. 1621-1633 - Bernhard Haeupler, D. Ellis Hershkowitz, Zihan Tan:
New Structures and Algorithms for Length-Constrained Expander Decompositions. 1634-1645 - Yeshwanth Cherapanamjeri:
Computing Approximate Centerpoints in Polynomial Time. 1654-1668 - Sanjeev Khanna, Aaron Putterman, Madhu Sudan:
Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. 1669-1706 - Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn:
Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. 1707-1723 - Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, Alon Hovav:
Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications. 1724-1767 - Eric Price, Zhiyang Xun:
Spectral Guarantees for Adversarial Streaming PCA. 1768-1785 - Tal Yankovitz:
A Stronger Bound for Linear 3-LCC. 1786-1801 - Pravesh K. Kothari, Peter Manohar:
Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. 1802-1845 - Zeyu Guo, Chaoping Xing, Chen Yuan, Zihan Zhang:
Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric. 1846-1873 - Omar Alrabiah, Venkatesan Guruswami:
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. 1874-1882 - Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan:
An Improved Line-Point Low-Degree Test. 1883-1892 - Caleb Koch, Carmen Strassle, Li-Yang Tan:
Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems. 1893-1910 - Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Gaussian Approximation of Convex Sets by Intersections of Halfspaces. 1911-1930 - Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis:
Agnostically Learning Multi-Index Models with Queries. 1931-1952 - Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning. 1953-1967 - Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy:
Revisiting Agnostic PAC Learning. 1968-1982 - Simone Fioravanti, Steve Hanneke, Shay Moran, Hilla Schefler, Iska Tsubari:
Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem. 1983-2009 - Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva:
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality. 2010-2032 - Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak:
Dynamic Deterministic Constant-Approximate Distance Oracles with nε Worst-Case Update Time. 2033-2044 - Dominik Kempa, Tomasz Kociumaka:
Lempel-Ziv (LZ77) Factorization in Sublinear Time. 2045-2055 - Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, Ta-Wei Tu:
Maximum Flow by Augmenting Paths in n2+o(1) Time. 2056-2077 - Arnold Filtser, Gramoz Goranci, Neel Patel, Maximilian Probst Gutenberg:
Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs. 2078-2098 - Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek:
Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps. 2099-2130 - Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski:
Verifying Groups in Linear Time. 2131-2147 - Mohsen Ghaffari, Christoph Grunau:
Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS. 2148-2179 - Yasunori Kinoshita, Baitian Li:
Power Series Composition in Near-Linear Time. 2180-2185 - Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang:
Faster (Δ+1)-Edge Coloring: Breaking the m√n Time Barrier. 2186-2201 - Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang:
An Improved Pseudopolynomial Time Algorithm for Subset Sum. 2202-2216 - George Giakkoupis, Marcos Kiwi, Dimitrios Los:
Naively Sorting Evolving Data is Optimal and Robust. 2217-2242 - Ivor van der Hoog, Daniel Rutschmann:
Tight Bounds for Sorting Under Partial Information. 2243-2252 - Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, Michael E. Saks:
Nearly Optimal List Labeling. 2253-2274 - Ziyun Chen, Zhiyi Huang, Enze Sun:
Stochastic Online Correlated Selection. 2275-2294 - Renato Ferreira Pinto Jr.:
Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach. 2295-2305 - Krishnamurthy Dj Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, Abhradeep Thakurta:
Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy. 2306-2317 - Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches. 2318-2343 - Zhiyan Ding, Ethan N. Epperly, Lin Lin, Ruizhe Zhang:
The ESPRIT Algorithm Under High Noise: Optimal Error Scaling and Noisy Super-Resolution. 2344-2366 - Robert Andrews, Avi Wigderson:
Constant-Depth Arithmetic Circuits for Linear Algebra Problems. 2367-2386 - Hiroshi Hirai, Keiya Sakabe:
Gradient Descent for Unbounded Convex Functions on Hadamard Manifolds and its Applications to Scaling Problems. 2387-2402 - Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam:
On the Complexity of Avoiding Heavy Elements. 2403-2412 - Moïse Blanchard:
Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems. 2413-2435
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:23 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:
