Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSearch dblp for Publications
export results for "toc:db/conf/focs/focs2023.bht:"
download as .bib file
@inproceedings{DBLP:conf/focs/00010W0Y23,
author = {Weiming Feng and
Heng Guo and
Chunyang Wang and
Jiaheng Wang and
Yitong Yin},
title = {Towards derandomising Markov chain Monte Carlo},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1963--1990},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00120},
doi = {10.1109/FOCS57990.2023.00120},
timestamp = {Tue, 02 Jan 2024 14:56:14 +0100},
biburl = {https://dblp.org/rec/conf/focs/00010W0Y23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001CW23,
author = {Yang Cai and
Ziyun Chen and
Jinzhao Wu},
title = {Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive
Bidders},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {134--147},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00017},
doi = {10.1109/FOCS57990.2023.00017},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001CW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001GR23,
author = {Mohsen Ghaffari and
Christoph Grunau and
V{\'{a}}clav Rozhon},
title = {Work-Efficient Parallel Derandomization {I:} Chernoff-like Concentrations
via Pairwise Independence},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1551--1562},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00094},
doi = {10.1109/FOCS57990.2023.00094},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001GR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001H0TW23,
author = {Lijie Chen and
William M. Hoza and
Xin Lyu and
Avishay Tal and
Hongxun Wu},
title = {Weighted Pseudorandom Generators via Inverse Analysis of Random Walks
and Shortcutting},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1224--1239},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00072},
doi = {10.1109/FOCS57990.2023.00072},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001H0TW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001LORS23,
author = {Lijie Chen and
Zhenjian Lu and
Igor C. Oliveira and
Hanlin Ren and
Rahul Santhanam},
title = {Polynomial-Time Pseudodeterministic Construction of Primes},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1261--1270},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00074},
doi = {10.1109/FOCS57990.2023.00074},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/0001LORS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001MY23,
author = {Zachary Chase and
Shay Moran and
Amir Yehudayoff},
title = {Stability and Replicability in Learning},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2430--2439},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00148},
doi = {10.1109/FOCS57990.2023.00148},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001MY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001N023,
author = {Hiroshi Hirai and
Harold Nieuwboer and
Michael Walter},
title = {Interior-point methods on manifolds: theory and applications},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2021--2030},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00123},
doi = {10.1109/FOCS57990.2023.00123},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001N023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001PSY23,
author = {Anupam Gupta and
Madhusudhan Reddy Pittu and
Ola Svensson and
Rachel Yuan},
title = {The Price of Explainability for Clustering},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1131--1148},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00067},
doi = {10.1109/FOCS57990.2023.00067},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001PSY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001T023,
author = {Lijie Chen and
Roei Tell and
Ryan Williams},
title = {Derandomization vs Refutation: {A} Unified Framework for Characterizing
Derandomization},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1008--1047},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00062},
doi = {10.1109/FOCS57990.2023.00062},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/0001T023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001Z23,
author = {Michal Wlodarczyk and
Meirav Zehavi},
title = {Planar Disjoint Paths, Treewidth, and Kernels},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {649--662},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00044},
doi = {10.1109/FOCS57990.2023.00044},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001Z23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/00020W023,
author = {Zhao Song and
Baocheng Sun and
Omri Weinstein and
Ruizhe Zhang},
title = {Quartic Samples Suffice for Fourier Interpolation},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1414--1425},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00087},
doi = {10.1109/FOCS57990.2023.00087},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/00020W023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0002TWY23,
author = {Xin Lyu and
Avishay Tal and
Hongxun Wu and
Junzhao Yang},
title = {Tight Time-Space Lower Bounds for Constant-Pass Learning},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1195--1202},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00070},
doi = {10.1109/FOCS57990.2023.00070},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0002TWY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0003RT23,
author = {Itay Cohen and
Roy Roth and
Amnon Ta{-}Shma},
title = {{HDX} Condensers},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1649--1664},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00100},
doi = {10.1109/FOCS57990.2023.00100},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0003RT23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0014PY23,
author = {Xiao Liang and
Omkant Pandey and
Takashi Yamakawa},
title = {A New Approach to Post-Quantum Non-Malleability},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {568--579},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00041},
doi = {10.1109/FOCS57990.2023.00041},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0014PY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AbbasiBBCGKMSS23,
author = {Fateme Abbasi and
Sandip Banerjee and
Jaroslaw Byrka and
Parinya Chalermsook and
Ameet Gadekar and
Kamyar Khodamoradi and
D{\'{a}}niel Marx and
Roohani Sharma and
Joachim Spoerhase},
title = {Parameterized Approximation Schemes for Clustering with General Norm
Objectives},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1377--1399},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00085},
doi = {10.1109/FOCS57990.2023.00085},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AbbasiBBCGKMSS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AbbeS23,
author = {Emmanuel Abbe and
Colin Sandon},
title = {A proof that Reed-Muller codes achieve Shannon capacity on symmetric
channels},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {177--193},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00020},
doi = {10.1109/FOCS57990.2023.00020},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AbbeS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Abboud0PS23,
author = {Amir Abboud and
Jason Li and
Debmalya Panigrahi and
Thatchaphol Saranurak},
title = {All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu
Trees in Almost-Linear Time},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2204--2212},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00137},
doi = {10.1109/FOCS57990.2023.00137},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Abboud0PS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AcuavivaMNPS0W23,
author = {Arturo Acuaviva and
Visu Makam and
Harold Nieuwboer and
David P{\'{e}}rez{-}Garc{\'{\i}}a and
Friedrich Sittner and
Michael Walter and
Freek Witteveen},
title = {The minimal canonical form of a tensor network},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {328--362},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00027},
doi = {10.1109/FOCS57990.2023.00027},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AcuavivaMNPS0W23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Aden-AliCSZ23,
author = {Ishaq Aden{-}Ali and
Yeshwanth Cherapanamjeri and
Abhishek Shetty and
Nikita Zhivotovskiy},
title = {Optimal {PAC} Bounds without Uniform Convergence},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1203--1223},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00071},
doi = {10.1109/FOCS57990.2023.00071},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Aden-AliCSZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Aggarwal023,
author = {Divesh Aggarwal and
Rajendra Kumar},
title = {Why we couldn't prove {SETH} hardness of the Closest Vector Problem
for even norms!},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2213--2230},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00138},
doi = {10.1109/FOCS57990.2023.00138},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Aggarwal023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AhmadinejadPPSV23,
author = {AmirMahdi Ahmadinejad and
John Peebles and
Edward Pyne and
Aaron Sidford and
Salil P. Vadhan},
title = {Singular Value Approximation and Sparsifying Random Walks on Directed
Graphs},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {846--854},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00054},
doi = {10.1109/FOCS57990.2023.00054},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AhmadinejadPPSV23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AlmanZ23,
author = {Josh Alman and
Hengjie Zhang},
title = {Generalizations of Matrix Multiplication can solve the Light Bulb
Problem},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1471--1495},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00090},
doi = {10.1109/FOCS57990.2023.00090},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AlmanZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AltschulerC23,
author = {Jason M. Altschuler and
Sinho Chewi},
title = {Faster high-accuracy log-concave sampling via algorithmic warm starts},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2169--2176},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00134},
doi = {10.1109/FOCS57990.2023.00134},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AltschulerC23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AndoniZ23,
author = {Alexandr Andoni and
Hengjie Zhang},
title = {Sub-quadratic (1+{\unicode{1013}})-approximate Euclidean Spanners,
with Applications},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {98--112},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00014},
doi = {10.1109/FOCS57990.2023.00014},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AndoniZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ApplebaumN23,
author = {Benny Applebaum and
Oded Nir},
title = {Advisor-Verifier-Prover Games and the Hardness of Information Theoretic
Cryptography},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {539--555},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00039},
doi = {10.1109/FOCS57990.2023.00039},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ApplebaumN23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ArnonCY23,
author = {Gal Arnon and
Alessandro Chiesa and
Eylon Yogev},
title = {IOPs with Inverse Polynomial Soundness Error},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {752--761},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00050},
doi = {10.1109/FOCS57990.2023.00050},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ArnonCY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AssadiS23,
author = {Sepehr Assadi and
Janani Sundaresan},
title = {Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds
for Approximate Matchings},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {909--932},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00058},
doi = {10.1109/FOCS57990.2023.00058},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AssadiS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BabbushBKSW23,
author = {Ryan Babbush and
Dominic W. Berry and
Robin Kothari and
Rolando D. Somma and
Nathan Wiebe},
title = {Exponential quantum speedup in simulating coupled classical oscillators\({}^{\mbox{*}}\)},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {405--414},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00030},
doi = {10.1109/FOCS57990.2023.00030},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BabbushBKSW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BakshiN23,
author = {Ainesh Bakshi and
Shyam Narayanan},
title = {Krylov Methods are (nearly) Optimal for Low-Rank Approximation},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2093--2101},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00128},
doi = {10.1109/FOCS57990.2023.00128},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BakshiN23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BallGDM23,
author = {Marshall Ball and
Eli Goldin and
Dana Dachman{-}Soled and
Saachi Mutreja},
title = {Extracting Randomness from Samplable Distributions, Revisited},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1505--1514},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00092},
doi = {10.1109/FOCS57990.2023.00092},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BallGDM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BallLMP23,
author = {Marshall Ball and
Yanyi Liu and
Noam Mazor and
Rafael Pass},
title = {Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity
and Key-Agreement},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {458--483},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00034},
doi = {10.1109/FOCS57990.2023.00034},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BallLMP23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BehnezhadRR23,
author = {Soheil Behnezhad and
Mohammad Roghani and
Aviad Rubinstein},
title = {Local Computation Algorithms for Maximum Matching: New Lower Bounds},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2322--2335},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00143},
doi = {10.1109/FOCS57990.2023.00143},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BehnezhadRR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Bercea0KHT23,
author = {Ioana O. Bercea and
Lorenzo Beretta and
Jonas Klausen and
Jakob B{\ae}k Tejs Houen and
Mikkel Thorup},
title = {Locally Uniform Hashing},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1440--1470},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00089},
doi = {10.1109/FOCS57990.2023.00089},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/Bercea0KHT23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BhattacharyaBLS23,
author = {Sayan Bhattacharya and
Niv Buchbinder and
Roie Levin and
Thatchaphol Saranurak},
title = {Chasing Positive Bodies},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1694--1714},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00103},
doi = {10.1109/FOCS57990.2023.00103},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BhattacharyaBLS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BhattacharyaKS23,
author = {Sayan Bhattacharya and
Peter Kiss and
Thatchaphol Saranurak},
title = {Dynamic (1+{\unicode{1013}})-Approximate Matching Size in Truly Sublinear
Update Time},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1563--1588},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00095},
doi = {10.1109/FOCS57990.2023.00095},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BhattacharyaKS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BlackC023,
author = {Hadley Black and
Deeparnab Chakrabarty and
C. Seshadhri},
title = {A d\({}^{\mbox{1/2+o(1)}}\) Monotonicity Tester for Boolean Functions
on d-Dimensional Hypergrids},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1796--1821},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00110},
doi = {10.1109/FOCS57990.2023.00110},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BlackC023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BlaisS23,
author = {Eric Blais and
Cameron Seth},
title = {Testing Graph Properties with the Container Method},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1787--1795},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00109},
doi = {10.1109/FOCS57990.2023.00109},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BlaisS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BlancKST23,
author = {Guy Blanc and
Caleb Koch and
Carmen Strassle and
Li{-}Yang Tan},
title = {A strong composition theorem for junta complexity and the boosting
of property testers},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1757--1777},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00107},
doi = {10.1109/FOCS57990.2023.00107},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BlancKST23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BlancaG23,
author = {Antonio Blanca and
Reza Gheissari},
title = {Sampling from the Potts model at low temperatures via Swendsen-Wang
dynamics},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2006--2020},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00122},
doi = {10.1109/FOCS57990.2023.00122},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BlancaG23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BodwinH23,
author = {Greg Bodwin and
Gary Hoppenworth},
title = {Folklore Sampling is Optimal for Exact Hopsets: Confirming the {\(\surd\)}n
Barrier},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {701--720},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00046},
doi = {10.1109/FOCS57990.2023.00046},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BodwinH23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BodwinHT23,
author = {Greg Bodwin and
Gary Hoppenworth and
Ohad Trabelsi},
title = {Bridge Girth: {A} Unifying Notion in Network Design},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {600--648},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00043},
doi = {10.1109/FOCS57990.2023.00043},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BodwinHT23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BozzaiRR23,
author = {Rainie Bozzai and
Victor Reis and
Thomas Rothvoss},
title = {The Vector Balancing Constant for Zonotopes},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1292--1300},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00077},
doi = {10.1109/FOCS57990.2023.00077},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BozzaiRR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BrakensiekHPZ23,
author = {Joshua Brakensiek and
Neng Huang and
Aaron Potechin and
Uri Zwick},
title = {Separating {MAX} 2-AND, {MAX} {DI-CUT} and {MAX} {CUT}},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {234--252},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00023},
doi = {10.1109/FOCS57990.2023.00023},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BrakensiekHPZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Brand0PKLGSS23,
author = {Jan van den Brand and
Li Chen and
Richard Peng and
Rasmus Kyng and
Yang P. Liu and
Maximilian Probst Gutenberg and
Sushant Sachdeva and
Aaron Sidford},
title = {A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {503--514},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00037},
doi = {10.1109/FOCS57990.2023.00037},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Brand0PKLGSS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BrandK23,
author = {Jan van den Brand and
Adam Karczmarz},
title = {Deterministic Fully Dynamic {SSSP} and More},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2312--2321},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00142},
doi = {10.1109/FOCS57990.2023.00142},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BrandK23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BrandZ23,
author = {Jan van den Brand and
Daniel J. Zhang},
title = {Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {493--502},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00036},
doi = {10.1109/FOCS57990.2023.00036},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BrandZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BravermanKM23,
author = {Mark Braverman and
Subhash Khot and
Dor Minzer},
title = {Parallel Repetition for the {GHZ} Game: Exponential Decay},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1337--1341},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00080},
doi = {10.1109/FOCS57990.2023.00080},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BravermanKM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BreslerGP23,
author = {Guy Bresler and
Chenghao Guo and
Yury Polyanskiy},
title = {Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs:
The Case of Extra Triangles},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2149--2158},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00132},
doi = {10.1109/FOCS57990.2023.00132},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BreslerGP23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BringmannCF23,
author = {Karl Bringmann and
Alejandro Cassis and
Nick Fischer},
title = {Negative-Weight Single-Source Shortest Paths in Near-Linear Time:
Now Faster!},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {515--538},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00038},
doi = {10.1109/FOCS57990.2023.00038},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BringmannCF23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BrowneKMP23,
author = {Reilly Browne and
Prahlad Narasimhan Kasthurirangan and
Joseph S. B. Mitchell and
Valentin Polishchuk},
title = {Constant-Factor Approximation Algorithms for Convex Cover and Hidden
Set in a Simple Polygon},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1357--1365},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00083},
doi = {10.1109/FOCS57990.2023.00083},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BrowneKMP23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BuschCFHHR23,
author = {Costas Busch and
Da Qi Chen and
Arnold Filtser and
Daniel Hathcock and
D. Ellis Hershkowitz and
Rajmohan Rajaraman},
title = {One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {60--76},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00012},
doi = {10.1109/FOCS57990.2023.00012},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BuschCFHHR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CanonneH0LN23,
author = {Cl{\'{e}}ment L. Canonne and
Samuel B. Hopkins and
Jerry Li and
Allen Liu and
Shyam Narayanan},
title = {The Full Landscape of Robust Mean Testing: Sharp Separations between
Oblivious and Adaptive Contamination},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2159--2168},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00133},
doi = {10.1109/FOCS57990.2023.00133},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CanonneH0LN23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CarmesinK23,
author = {Johannes Carmesin and
Jan Kurkofka},
title = {Canonical decompositions of 3-connected graphs},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1887--1920},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00115},
doi = {10.1109/FOCS57990.2023.00115},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CarmesinK23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CarmonJJLLST23,
author = {Yair Carmon and
Arun Jambulapati and
Yujia Jin and
Yin Tat Lee and
Daogao Liu and
Aaron Sidford and
Kevin Tian},
title = {ReSQueing Parallel and Private Stochastic Convex Optimization},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2031--2058},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00124},
doi = {10.1109/FOCS57990.2023.00124},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CarmonJJLLST23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CassisKW23,
author = {Alejandro Cassis and
Tomasz Kociumaka and
Philip Wellnitz},
title = {Optimal Algorithms for Bounded Weighted Edit Distance},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2177--2187},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00135},
doi = {10.1109/FOCS57990.2023.00135},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/CassisKW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Chan0WX23,
author = {Timothy M. Chan and
Ce Jin and
Virginia Vassilevska Williams and
Yinzhan Xu},
title = {Faster Algorithms for Text-to-Pattern Hamming Distances},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2188--2203},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00136},
doi = {10.1109/FOCS57990.2023.00136},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Chan0WX23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChangCLMST23,
author = {Hsien{-}Chih Chang and
Jonathan Conroy and
Hung Le and
Lazar Milenkovic and
Shay Solomon and
Cuong Than},
title = {Covering Planar Metrics (and Beyond): {O(1)} Trees Suffice},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2231--2261},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00139},
doi = {10.1109/FOCS57990.2023.00139},
timestamp = {Sun, 05 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ChangCLMST23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChatziafratisM23,
author = {Vaggos Chatziafratis and
Konstantin Makarychev},
title = {Triplet Reconstruction and all other Phylogenetic CSPs are Approximation
Resistant},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {253--284},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00024},
doi = {10.1109/FOCS57990.2023.00024},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChatziafratisM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Chen0Y23,
author = {Xiaoyu Chen and
Jingcheng Liu and
Yitong Yin},
title = {Uniqueness and Rapid Mixing in the Bipartite Hardcore Model (extended
abstract)},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1991--2005},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00121},
doi = {10.1109/FOCS57990.2023.00121},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Chen0Y23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenH0LS23,
author = {Sitan Chen and
Brice Huang and
Jerry Li and
Allen Liu and
Mark Sellke},
title = {When Does Adaptivity Help for Quantum State Learning?},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {391--404},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00029},
doi = {10.1109/FOCS57990.2023.00029},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenH0LS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenLMM23,
author = {Zongchen Chen and
Kuikui Liu and
Nitya Mani and
Ankur Moitra},
title = {Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {810--845},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00053},
doi = {10.1109/FOCS57990.2023.00053},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenLMM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenP23,
author = {Xi Chen and
Binghui Peng},
title = {Memory-Query Tradeoffs for Randomized Convex Optimization},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1400--1413},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00086},
doi = {10.1109/FOCS57990.2023.00086},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenP23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenP23a,
author = {Xi Chen and
Shyamal Patel},
title = {New Lower Bounds for Adaptive Tolerant Junta Testing},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1778--1786},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00108},
doi = {10.1109/FOCS57990.2023.00108},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenP23a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChewiP00N23,
author = {Sinho Chewi and
Jaume de Dios Pont and
Jerry Li and
Chen Lu and
Shyam Narayanan},
title = {Query lower bounds for log-concave sampling},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2139--2148},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00131},
doi = {10.1109/FOCS57990.2023.00131},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChewiP00N23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CiniW23,
author = {Valerio Cini and
Hoeteck Wee},
title = {{ABE} for Circuits with poly ({\(\lambda\)}) -sized Keys from {LWE}},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {435--446},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00032},
doi = {10.1109/FOCS57990.2023.00032},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CiniW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Cohen-AddadL0N23,
author = {Vincent Cohen{-}Addad and
Euiwoong Lee and
Shi Li and
Alantha Newman},
title = {Handling Correlated Rounding Error via Preclustering: {A} 1.73-approximation
for Correlation Clustering},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1082--1104},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00065},
doi = {10.1109/FOCS57990.2023.00065},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Cohen-AddadL0N23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Cohen-AddadLPP23,
author = {Vincent Cohen{-}Addad and
Hung Le and
Marcin Pilipczuk and
Michal Pilipczuk},
title = {Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic
Treewidth with Expected Multiplicative Distortion Arbitrarily Close
to 1},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2262--2277},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00140},
doi = {10.1109/FOCS57990.2023.00140},
timestamp = {Sun, 05 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/Cohen-AddadLPP23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Cohen-AddadSS23,
author = {Vincent Cohen{-}Addad and
David Saulpic and
Chris Schwiegelshohn},
title = {Deterministic Clustering in High Dimensional Spaces: Sketches and
Approximation},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1105--1130},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00066},
doi = {10.1109/FOCS57990.2023.00066},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Cohen-AddadSS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Cohen-AddadWZ23,
author = {Vincent Cohen{-}Addad and
David P. Woodruff and
Samson Zhou},
title = {Streaming Euclidean k-median and k-means with o(log n) Space},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {883--908},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00057},
doi = {10.1109/FOCS57990.2023.00057},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Cohen-AddadWZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ConnerydRNPR23,
author = {Jonas Conneryd and
Susanna F. de Rezende and
Jakob Nordstr{\"{o}}m and
Shuo Pang and
Kilian Risse},
title = {Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1--11},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00007},
doi = {10.1109/FOCS57990.2023.00007},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ConnerydRNPR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DuanMSY23,
author = {Ran Duan and
Jiayi Mao and
Xinkai Shu and
Longhui Yin},
title = {A Randomized Algorithm for Single-Source Shortest Path on Undirected
Real-Weighted Graphs},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {484--492},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00035},
doi = {10.1109/FOCS57990.2023.00035},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DuanMSY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DuanWZ23,
author = {Ran Duan and
Hongxun Wu and
Renfei Zhou},
title = {Faster Matrix Multiplication via Asymmetric Hashing},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2129--2138},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00130},
doi = {10.1109/FOCS57990.2023.00130},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DuanWZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DujmovicEMW23,
author = {Vida Dujmovic and
Louis Esperet and
Pat Morin and
David R. Wood},
title = {Proof of the Clustered Hadwiger Conjecture},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1921--1930},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00116},
doi = {10.1109/FOCS57990.2023.00116},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DujmovicEMW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/EdenFGMM23,
author = {Alon Eden and
Michal Feldman and
Kira Goldner and
Simon Mauras and
Divyarthi Mohan},
title = {Constant Approximation for Private Interdependent Valuations},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {148--163},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00018},
doi = {10.1109/FOCS57990.2023.00018},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/EdenFGMM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ElkinS23,
author = {Michael Elkin and
Idan Shabat},
title = {Path-Reporting Distance Oracles with Logarithmic Stretch and Size
O(n log log n)},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2278--2311},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00141},
doi = {10.1109/FOCS57990.2023.00141},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ElkinS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FoxL23,
author = {Emily Fox and
Jiashuai Lu},
title = {A deterministic near-linear time approximation scheme for geometric
transportation},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1301--1315},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00078},
doi = {10.1109/FOCS57990.2023.00078},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/FoxL23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ghadiri23,
author = {Mehrdad Ghadiri},
title = {On Symmetric Factorizations of Hankel Matrices},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2081--2092},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00127},
doi = {10.1109/FOCS57990.2023.00127},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ghadiri23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GhadiriPV23,
author = {Mehrdad Ghadiri and
Richard Peng and
Santosh S. Vempala},
title = {The Bit Complexity of Efficient Continuous Optimization},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2059--2070},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00125},
doi = {10.1109/FOCS57990.2023.00125},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GhadiriPV23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GhaziIK0M23,
author = {Badih Ghazi and
Rahul Ilango and
Pritish Kamath and
Ravi Kumar and
Pasin Manurangsi},
title = {Towards Separating Computational and Statistical Differential Privacy},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {580--599},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00042},
doi = {10.1109/FOCS57990.2023.00042},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GhaziIK0M23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GhoshHH0S23,
author = {Sumanta Ghosh and
Prahladh Harsha and
Simao Herdade and
Mrinal Kumar and
Ramprasad Saptharishi},
title = {Fast Numerical Multivariate Multipoint Evaluation},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1426--1439},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00088},
doi = {10.1109/FOCS57990.2023.00088},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GhoshHH0S23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GhoshalL23,
author = {Suprovat Ghoshal and
Euiwoong Lee},
title = {On Lifting Integrality Gaps to {SSEH} Hardness for Globally Constrained
CSPs},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {26--36},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00009},
doi = {10.1109/FOCS57990.2023.00009},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GhoshalL23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GirishST023,
author = {Uma Girish and
Makrand Sinha and
Avishay Tal and
Kewen Wu},
title = {Fourier Growth of Communication Protocols for {XOR} Functions},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {721--732},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00047},
doi = {10.1109/FOCS57990.2023.00047},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GirishST023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Golowich23,
author = {Louis Golowich},
title = {From Grassmannian to Simplicial High-Dimensional Expanders},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1639--1648},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00099},
doi = {10.1109/FOCS57990.2023.00099},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Golowich23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GoosRS023,
author = {Mika G{\"{o}}{\"{o}}s and
Artur Riazanov and
Anastasia Sofronova and
Dmitry Sokolov},
title = {Top-Down Lower Bounds for Depth-Four Circuits},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1048--1055},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00063},
doi = {10.1109/FOCS57990.2023.00063},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GoosRS023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GraurJS23,
author = {Andrei Graur and
Haotian Jiang and
Aaron Sidford},
title = {Sparse Submodular Function Minimization},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2071--2080},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00126},
doi = {10.1109/FOCS57990.2023.00126},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GraurJS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GravinST23,
author = {Nick Gravin and
Enze Sun and
Zhihao Gavin Tang},
title = {Online Ordinal Problems: Optimality of Comparison-based Algorithms
and their Cardinal Complexity},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1863--1876},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00113},
doi = {10.1109/FOCS57990.2023.00113},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GravinST23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GroheLNS23,
author = {Martin Grohe and
Moritz Lichter and
Daniel Neuen and
Pascal Schweitzer},
title = {Compressing {CFI} Graphs and Lower Bounds for the Weisfeiler-Leman
Refinements},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {798--809},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00052},
doi = {10.1109/FOCS57990.2023.00052},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GroheLNS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GrossmanGS23,
author = {Ofer Grossman and
Meghal Gupta and
Mark Sellke},
title = {Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1496--1504},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00091},
doi = {10.1109/FOCS57990.2023.00091},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GrossmanGS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GuoZ23,
author = {Zeyu Guo and
Zihan Zhang},
title = {Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity
over Polynomial-Size Alphabets},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {164--176},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00019},
doi = {10.1109/FOCS57990.2023.00019},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/GuoZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GuruswamiHKM23,
author = {Venkatesan Guruswami and
Jun{-}Ting Hsieh and
Pravesh K. Kothari and
Peter Manohar},
title = {Efficient Algorithms for Semirandom Planted CSPs at the Refutation
Threshold},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {307--327},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00026},
doi = {10.1109/FOCS57990.2023.00026},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GuruswamiHKM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HaahKOT23,
author = {Jeongwan Haah and
Robin Kothari and
Ryan O'Donnell and
Ewin Tang},
title = {Query-optimal estimation of unitary channels in diamond distance},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {363--390},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00028},
doi = {10.1109/FOCS57990.2023.00028},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HaahKOT23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Hastad23,
author = {Johan H{\aa}stad},
title = {On small-depth Frege proofs for {PHP}},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {37--49},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00010},
doi = {10.1109/FOCS57990.2023.00010},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Hastad23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HermanR23,
author = {Tal Herman and
Guy N. Rothblum},
title = {Doubley-Efficient Interactive Proofs for Distribution Properties},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {743--751},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00049},
doi = {10.1109/FOCS57990.2023.00049},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HermanR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HiraharaN23,
author = {Shuichi Hirahara and
Mikito Nanashima},
title = {Learning in Pessiland via Inductive Inference},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {447--457},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00033},
doi = {10.1109/FOCS57990.2023.00033},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HiraharaN23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HollenderR23,
author = {Alexandros Hollender and
Aviad Rubinstein},
title = {Envy-Free Cake-Cutting for Four Agents},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {113--122},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00015},
doi = {10.1109/FOCS57990.2023.00015},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HollenderR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HsiehLL23,
author = {Yao{-}Ching Hsieh and
Huijia Lin and
Ji Luo},
title = {Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {415--434},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00031},
doi = {10.1109/FOCS57990.2023.00031},
timestamp = {Wed, 07 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HsiehLL23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ilango23,
author = {Rahul Ilango},
title = {{SAT} Reduces to the Minimum Circuit Size Problem with a Random Oracle},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {733--742},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00048},
doi = {10.1109/FOCS57990.2023.00048},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ilango23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JainMPV23,
author = {Vishesh Jain and
Marcus Michelen and
Huy Tuan Pham and
Thuy{-}Duong Vuong},
title = {Optimal mixing of the down-up walk on independent sets of a given
size},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1665--1681},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00101},
doi = {10.1109/FOCS57990.2023.00101},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JainMPV23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JambulapatiLLS23,
author = {Arun Jambulapati and
James R. Lee and
Yang P. Liu and
Aaron Sidford},
title = {Sparsifying Sums of Norms},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1953--1962},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00119},
doi = {10.1109/FOCS57990.2023.00119},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JambulapatiLLS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JeronimoST23,
author = {Fernando Granha Jeronimo and
Shashank Srivastava and
Madhur Tulsiani},
title = {List Decoding of Tanner and Expander Amplified Codes from Distance
Certificates},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1682--1693},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00102},
doi = {10.1109/FOCS57990.2023.00102},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JeronimoST23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JiaKV23,
author = {He Jia and
Pravesh K. Kothari and
Santosh S. Vempala},
title = {Beyond Moments: Robustly Learning Affine Transformations with Asymptotically
Optimal Error},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2408--2429},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00147},
doi = {10.1109/FOCS57990.2023.00147},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JiaKV23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JiangPW23,
author = {Shunhua Jiang and
Binghui Peng and
Omri Weinstein},
title = {The Complexity of Dynamic Least-Squares Regression},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1605--1627},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00097},
doi = {10.1109/FOCS57990.2023.00097},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JiangPW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JohnstonLV23,
author = {Nathaniel Johnston and
Benjamin Lovitz and
Aravindan Vijayaraghavan},
title = {Computing linear sections of varieties: quantum entanglement, tensor
decompositions and beyond},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1316--1336},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00079},
doi = {10.1109/FOCS57990.2023.00079},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JohnstonLV23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JungeblutMU23,
author = {Paul Jungeblut and
Laura Merker and
Torsten Ueckerdt},
title = {Directed Acyclic Outerplanar Graphs Have Constant Stack Number},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1937--1952},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00118},
doi = {10.1109/FOCS57990.2023.00118},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/JungeblutMU23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KachamPTW23,
author = {Praneeth Kacham and
Rasmus Pagh and
Mikkel Thorup and
David P. Woodruff},
title = {Pseudorandom Hashing for Space-bounded Computation with Applications
in Streaming},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1515--1550},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00093},
doi = {10.1109/FOCS57990.2023.00093},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/KachamPTW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KarczmarzS23,
author = {Adam Karczmarz and
Piotr Sankowski},
title = {Sensitivity and Dynamic Distance Oracles via Generic Matrices and
Frobenius Form},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1745--1756},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00106},
doi = {10.1109/FOCS57990.2023.00106},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KarczmarzS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KelleyM23,
author = {Zander Kelley and
Raghu Meka},
title = {Strong Bounds for 3-Progressions},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {933--973},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00059},
doi = {10.1109/FOCS57990.2023.00059},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KelleyM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Kelner0LST23,
author = {Jonathan A. Kelner and
Jerry Li and
Allen Liu and
Aaron Sidford and
Kevin Tian},
title = {Matrix Completion in Almost-Verification Time},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2102--2128},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00129},
doi = {10.1109/FOCS57990.2023.00129},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Kelner0LST23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KempaK23,
author = {Dominik Kempa and
Tomasz Kociumaka},
title = {Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays
in Optimal Compressed Space},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1877--1886},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00114},
doi = {10.1109/FOCS57990.2023.00114},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KempaK23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Klein23,
author = {Ohad Klein},
title = {Slicing all Edges of an n-cube Requires n\({}^{\mbox{2/3}}\) Hyperplanes},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1931--1936},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00117},
doi = {10.1109/FOCS57990.2023.00117},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Klein23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KleinO23,
author = {Nathan Klein and
Neil Olver},
title = {Thin Trees for Laminar Families},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {50--59},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00011},
doi = {10.1109/FOCS57990.2023.00011},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KleinO23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KochST23,
author = {Caleb Koch and
Carmen Strassle and
Li{-}Yang Tan},
title = {Properly learning decision trees with queries is NP-hard},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2383--2407},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00146},
doi = {10.1109/FOCS57990.2023.00146},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KochST23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Kociumaka0S23,
author = {Tomasz Kociumaka and
Anish Mukherjee and
Barna Saha},
title = {Approximating Edit Distance in the Fully Dynamic Model},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1628--1638},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00098},
doi = {10.1109/FOCS57990.2023.00098},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Kociumaka0S23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KorhonenMNP023,
author = {Tuukka Korhonen and
Konrad Majewski and
Wojciech Nadara and
Michal Pilipczuk and
Marek Sokolowski},
title = {Dynamic treewidth},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1734--1744},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00105},
doi = {10.1109/FOCS57990.2023.00105},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/KorhonenMNP023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KulikMS23,
author = {Ariel Kulik and
Matthias Mnich and
Hadas Shachnai},
title = {Improved Approximations for Vector Bin Packing via Iterative Randomized
Rounding},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1366--1376},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00084},
doi = {10.1109/FOCS57990.2023.00084},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KulikMS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KumabeY23,
author = {Soh Kumabe and
Yuichi Yoshida},
title = {Lipschitz Continuous Algorithms for Graph Problems},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {762--797},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00051},
doi = {10.1109/FOCS57990.2023.00051},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KumabeY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Kuszmaul23,
author = {William Kuszmaul},
title = {Strongly History-Independent Storage Allocation: New Upper and Lower
Bounds},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1822--1841},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00111},
doi = {10.1109/FOCS57990.2023.00111},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Kuszmaul23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LangeV23,
author = {Jane Lange and
Arsen Vasilyan},
title = {Agnostic proper learning of monotone functions: beyond the black-box
correction barrier},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1149--1170},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00068},
doi = {10.1109/FOCS57990.2023.00068},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LangeV23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LarsenY23,
author = {Kasper Green Larsen and
Huacheng Yu},
title = {Super-Logarithmic Lower Bounds for Dynamic Graph Problems},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1589--1604},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00096},
doi = {10.1109/FOCS57990.2023.00096},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LarsenY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LeST23,
author = {Hung Le and
Shay Solomon and
Cuong Than},
title = {Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics:
Breaking the {\(\Omega\)} (log n) Lightness Barrier},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {77--97},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00013},
doi = {10.1109/FOCS57990.2023.00013},
timestamp = {Sun, 05 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/LeST23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Li23,
author = {Xin Li},
title = {Two Source Extractors for Asymptotically Optimal Entropy, and (Many)
More},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1271--1281},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00075},
doi = {10.1109/FOCS57990.2023.00075},
timestamp = {Sat, 13 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/Li23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LiLYZ23,
author = {Tianxiao Li and
Jingxun Liang and
Huacheng Yu and
Renfei Zhou},
title = {Dynamic "Succincter"},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1715--1733},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00104},
doi = {10.1109/FOCS57990.2023.00104},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LiLYZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LiLYZ23a,
author = {Tianxiao Li and
Jingxun Liang and
Huacheng Yu and
Renfei Zhou},
title = {Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1842--1862},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00112},
doi = {10.1109/FOCS57990.2023.00112},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LiLYZ23a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LinRSW23,
author = {Bingkai Lin and
Xuandi Ren and
Yican Sun and
Xiuhan Wang},
title = {Improved Hardness of Approximating k-Clique under {ETH}},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {285--306},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00025},
doi = {10.1109/FOCS57990.2023.00025},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/LinRSW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LovettZ23,
author = {Shachar Lovett and
Jiapeng Zhang},
title = {Streaming Lower Bounds and Asymmetric Set-Disjointness},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {871--882},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00056},
doi = {10.1109/FOCS57990.2023.00056},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LovettZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Meir23,
author = {Or Meir},
title = {Toward Better Depth Lower Bounds: {A} KRW-like theorem for Strong
Composition},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1056--1081},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00064},
doi = {10.1109/FOCS57990.2023.00064},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Meir23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/MerinoM23,
author = {Arturo I. Merino and
Torsten M{\"{u}}tze},
title = {Traversing combinatorial 0/1-polytopes via optimization},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1282--1291},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00076},
doi = {10.1109/FOCS57990.2023.00076},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/MerinoM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/MetgerY23,
author = {Tony Metger and
Henry Yuen},
title = {stateQIP = statePSPACE},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1349--1356},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00082},
doi = {10.1109/FOCS57990.2023.00082},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/MetgerY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/MinzerZ23,
author = {Dor Minzer and
Kai Zhe Zheng},
title = {Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {206--233},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00022},
doi = {10.1109/FOCS57990.2023.00022},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/MinzerZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/NatarajanZ23,
author = {Anand Natarajan and
Tina Zhang},
title = {Bounding the Quantum Value of Compiled Nonlocal Games: From {CHSH}
to {BQP} Verification},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1342--1348},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00081},
doi = {10.1109/FOCS57990.2023.00081},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/NatarajanZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ODonnellS023,
author = {Ryan O'Donnell and
Rocco A. Servedio and
Pedro Paredes},
title = {Explicit orthogonal and unitary designs},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1240--1260},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00073},
doi = {10.1109/FOCS57990.2023.00073},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ODonnellS023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/OlverSK23,
author = {Neil Olver and
Leon Sering and
Laura Vargas Koch},
title = {Convergence of Approximate and Packet Routing Equilibria to Nash Flows
Over Time},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {123--133},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00016},
doi = {10.1109/FOCS57990.2023.00016},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/OlverSK23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Parter23,
author = {Merav Parter},
title = {Secure Computation Meets Distributed Universal Optimality},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2336--2368},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00144},
doi = {10.1109/FOCS57990.2023.00144},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Parter23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/PengR23,
author = {Binghui Peng and
Aviad Rubinstein},
title = {Near Optimal Memory-Regret Tradeoff for Online Learning},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1171--1194},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00069},
doi = {10.1109/FOCS57990.2023.00069},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/PengR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/PyneRZ23,
author = {Edward Pyne and
Ran Raz and
Wei Zhan},
title = {Certified Hardness vs. Randomness for Log-Space},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {989--1007},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00061},
doi = {10.1109/FOCS57990.2023.00061},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/PyneRZ23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ReisR23,
author = {Victor Reis and
Thomas Rothvoss},
title = {The Subspace Flatness Conjecture and Faster Integer Programming},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {974--988},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00060},
doi = {10.1109/FOCS57990.2023.00060},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ReisR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/RezendePR23,
author = {Susanna F. de Rezende and
Aaron Potechin and
Kilian Risse},
title = {Clique Is Hard on Average for Unary Sherali-Adams},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {12--25},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00008},
doi = {10.1109/FOCS57990.2023.00008},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/RezendePR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/RichelsonR23,
author = {Silas Richelson and
Sourya Roy},
title = {Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal
Binary Codes},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {194--205},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00021},
doi = {10.1109/FOCS57990.2023.00021},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/RichelsonR23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/RuzomberkaNBP23,
author = {Eric Ruzomberka and
Homa Nikbakht and
Christopher G. Brinton and
H. Vincent Poor},
title = {On Pseudolinear Codes for Correcting Adversarial Errors},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {556--567},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00040},
doi = {10.1109/FOCS57990.2023.00040},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/RuzomberkaNBP23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/SahS23,
author = {Ashwin Sah and
Mehtaab Sawhney},
title = {Distribution of the threshold for the symmetric perceptron},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {2369--2382},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00145},
doi = {10.1109/FOCS57990.2023.00145},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/SahS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/SaxenaS0V23,
author = {Raghuvansh R. Saxena and
Noah G. Singer and
Madhu Sudan and
Santhoshini Velusamy},
title = {Improved Streaming Algorithms for Maximum Directed Cut via Smoothed
Snapshots},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {855--870},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00055},
doi = {10.1109/FOCS57990.2023.00055},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/SaxenaS0V23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Torunczyk23,
author = {Szymon Torunczyk},
title = {Flip-width: Cops and Robber on dense graphs},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {663--700},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00045},
doi = {10.1109/FOCS57990.2023.00045},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Torunczyk23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/focs/2023,
title = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023},
doi = {10.1109/FOCS57990.2023},
isbn = {979-8-3503-1894-4},
timestamp = {Tue, 02 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/2023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
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-06-03 21:13 CEST 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:
