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