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/focs2021.bht:"
download as .bib file
@proceedings{DBLP:conf/focs/2021,
title = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
publisher = {{IEEE}},
year = {2022},
url = {https://doi.org/10.1109/FOCS52979.2022},
doi = {10.1109/FOCS52979.2022},
isbn = {978-1-6654-2055-6},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/2021.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/00010P21,
author = {Anupam Gupta and
Amit Kumar and
Debmalya Panigrahi},
title = {A Hitting Set Relaxation for {\textdollar}k{\textdollar}-Server and
an Extension to Time-Windows},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {504--515},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00057},
doi = {10.1109/FOCS52979.2021.00057},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/00010P21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001JSW21,
author = {Lijie Chen and
Ce Jin and
Rahul Santhanam and
R. Ryan Williams},
title = {Constructive Separations and Their Consequences},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {646--657},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00069},
doi = {10.1109/FOCS52979.2021.00069},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/0001JSW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001K21,
author = {Rahul Jain and
Srijita Kundu},
title = {A direct product theorem for quantum communication complexity with
applications to device-independent {QKD}},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1285--1295},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00125},
doi = {10.1109/FOCS52979.2021.00125},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001K21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001KK21,
author = {George Christodoulou and
Elias Koutsoupias and
Annam{\'{a}}ria Kov{\'{a}}cs},
title = {On the Nisan-Ronen conjecture},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {839--850},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00086},
doi = {10.1109/FOCS52979.2021.00086},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/0001KK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001KL21,
author = {Anupam Gupta and
Gregory Kehne and
Roie Levin},
title = {Random Order Online Set Cover is as Easy as Offline},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1253--1264},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00122},
doi = {10.1109/FOCS52979.2021.00122},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001KL21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001S21,
author = {Wenyu Jin and
Xiaorui Sun},
title = {Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Extended
Abstract)},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {861--872},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00088},
doi = {10.1109/FOCS52979.2021.00088},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001S21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001T21,
author = {Lijie Chen and
Roei Tell},
title = {Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {125--136},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00021},
doi = {10.1109/FOCS52979.2021.00021},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001T21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001W21,
author = {Oded Goldreich and
Avi Wigderson},
title = {Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {269--275},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00035},
doi = {10.1109/FOCS52979.2021.00035},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001W21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0002R21,
author = {Marco Bressan and
Marc Roth},
title = {Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms,
Hardness Results, and Complexity Dichotomies},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {276--285},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00036},
doi = {10.1109/FOCS52979.2021.00036},
timestamp = {Sun, 12 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0002R21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0003SS21,
author = {Akash Kumar and
C. Seshadhri and
Andrew Stolman},
title = {Random walks and forbidden minors {III:} {\textdollar}{\textbackslash}text\{poly\}{\textbackslash}left(d{\textbackslash}varepsilon
\{-1\}{\textbackslash}right){\textdollar}-time partition oracles for
minor-free graph classes},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {257--268},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00034},
doi = {10.1109/FOCS52979.2021.00034},
timestamp = {Thu, 07 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/0003SS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0006PS21,
author = {Jason Li and
Debmalya Panigrahi and
Thatchaphol Saranurak},
title = {A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1124--1134},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00111},
doi = {10.1109/FOCS52979.2021.00111},
timestamp = {Sun, 12 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0006PS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AbbeLS21,
author = {Emmanuel Abbe and
Shuangping Li and
Allan Sly},
title = {Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric
Perceptron},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {327--338},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00041},
doi = {10.1109/FOCS52979.2021.00041},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AbbeLS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AbboudKT21,
author = {Amir Abboud and
Robert Krauthgamer and
Ohad Trabelsi},
title = {{APMF} {\textless} APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic
Time},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1135--1146},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00112},
doi = {10.1109/FOCS52979.2021.00112},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/AbboudKT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AbdolazimiLG21,
author = {Dorna Abdolazimi and
Kuikui Liu and
Shayan Oveis Gharan},
title = {A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications
to Sampling Colorings},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {161--172},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00024},
doi = {10.1109/FOCS52979.2021.00024},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AbdolazimiLG21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Abrahamsen21,
author = {Mikkel Abrahamsen},
title = {Covering Polygons is Even Harder},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {375--386},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00045},
doi = {10.1109/FOCS52979.2021.00045},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/Abrahamsen21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AkmalW21,
author = {Shyan Akmal and
Ryan Williams},
title = {{MAJORITY-3SAT} (and Related Problems) in Polynomial Time},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1033--1043},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00103},
doi = {10.1109/FOCS52979.2021.00103},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AkmalW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Allen-ZhuL21,
author = {Zeyuan Allen{-}Zhu and
Yuanzhi Li},
title = {Feature Purification: How Adversarial Training Performs Robust Deep
Learning},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {977--988},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00098},
doi = {10.1109/FOCS52979.2021.00098},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Allen-ZhuL21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AlonHHM21,
author = {Noga Alon and
Steve Hanneke and
Ron Holzman and
Shay Moran},
title = {A Theory of {PAC} Learnability of Partial Concept Classes},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {658--671},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00070},
doi = {10.1109/FOCS52979.2021.00070},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AlonHHM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ArunachalamGGOS21,
author = {Srinivasan Arunachalam and
Alex B. Grilo and
Tom Gur and
Igor C. Oliveira and
Aarthi Sundaram},
title = {Quantum learning algorithms imply circuit lower bounds},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {562--573},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00062},
doi = {10.1109/FOCS52979.2021.00062},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ArunachalamGGOS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AxiotisMV21,
author = {Kyriakos Axiotis and
Aleksander Madry and
Adrian Vladu},
title = {Faster Sparse Minimum Cost Flow by Electrical Flow Localization},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {528--539},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00059},
doi = {10.1109/FOCS52979.2021.00059},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AxiotisMV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BalodisBG0K21,
author = {Kaspars Balodis and
Shalev Ben{-}David and
Mika G{\"{o}}{\"{o}}s and
Siddhartha Jain and
Robin Kothari},
title = {Unambiguous DNFs and Alon-Saks-Seymour},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {116--124},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00020},
doi = {10.1109/FOCS52979.2021.00020},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BalodisBG0K21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BasuC21,
author = {Saugata Basu and
Nathanael Cox},
title = {Harmonic Persistent Homology (extended abstract)},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1112--1123},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00110},
doi = {10.1109/FOCS52979.2021.00110},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BasuC21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BeckerLM21,
author = {Oren Becker and
Alexander Lubotzky and
Jonathan Mosheiff},
title = {Testability of relations between permutations},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {286--297},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00037},
doi = {10.1109/FOCS52979.2021.00037},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BeckerLM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Behnezhad21,
author = {Soheil Behnezhad},
title = {Time-Optimal Sublinear Algorithms for Matching and Vertex Cover},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {873--884},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00089},
doi = {10.1109/FOCS52979.2021.00089},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Behnezhad21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BenderKK21,
author = {Michael A. Bender and
Bradley C. Kuszmaul and
William Kuszmaul},
title = {Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1171--1182},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00115},
doi = {10.1109/FOCS52979.2021.00115},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BenderKK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BernsteinGS21,
author = {Aaron Bernstein and
Maximilian Probst Gutenberg and
Thatchaphol Saranurak},
title = {Deterministic Decremental {SSSP} and Approximate Min-Cost Flow in
Almost-Linear Time},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1000--1008},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00100},
doi = {10.1109/FOCS52979.2021.00100},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BernsteinGS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BlancC21,
author = {Guy Blanc and
Moses Charikar},
title = {Multiway Online Correlated Selection},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1277--1284},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00124},
doi = {10.1109/FOCS52979.2021.00124},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BlancC21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BlancLQT21,
author = {Guy Blanc and
Jane Lange and
Mingda Qiao and
Li{-}Yang Tan},
title = {Properly learning decision trees in almost polynomial time},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {920--929},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00093},
doi = {10.1109/FOCS52979.2021.00093},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BlancLQT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BlockiCGLZZ21,
author = {Jeremiah Blocki and
Kuan Cheng and
Elena Grigorescu and
Xin Li and
Yu Zheng and
Minshen Zhu},
title = {Exponential Lower Bounds for Locally Decodable and Correctable Codes
for Insertions and Deletions},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {739--750},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00077},
doi = {10.1109/FOCS52979.2021.00077},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BlockiCGLZZ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BodlaenderGNS21,
author = {Hans L. Bodlaender and
Carla Groenland and
Jesper Nederlof and
C{\'{e}}line M. F. Swennenhuis},
title = {Parameterized Problems Complete for Nondeterministic {FPT} time and
Logarithmic Space},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {193--204},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00027},
doi = {10.1109/FOCS52979.2021.00027},
timestamp = {Thu, 23 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BodlaenderGNS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Boix-AdseraBK21,
author = {Enric Boix{-}Adser{\`{a}} and
Guy Bresler and
Frederic Koehler},
title = {Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {417--426},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00049},
doi = {10.1109/FOCS52979.2021.00049},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Boix-AdseraBK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BoulandFLL21,
author = {Adam Bouland and
Bill Fefferman and
Zeph Landau and
Yunchao Liu},
title = {Noise and the Frontier of Quantum Supremacy},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1308--1317},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00127},
doi = {10.1109/FOCS52979.2021.00127},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BoulandFLL21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BousquetBKEM21,
author = {Olivier Bousquet and
Mark Braverman and
Gillat Kol and
Klim Efremenko and
Shay Moran},
title = {Statistically Near-Optimal Hypothesis Selection},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {909--919},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00092},
doi = {10.1109/FOCS52979.2021.00092},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BousquetBKEM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BravermanGZ21,
author = {Mark Braverman and
Sumegha Garg and
Or Zamir},
title = {Tight Space Complexity of the Coin Problem},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1068--1079},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00106},
doi = {10.1109/FOCS52979.2021.00106},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BravermanGZ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BravermanKLM21,
author = {Mark Braverman and
Subhash Khot and
Noam Lifshitz and
Dor Minzer},
title = {An Invariance Principle for the Multi-slice, with Applications},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {228--236},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00030},
doi = {10.1109/FOCS52979.2021.00030},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BravermanKLM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BreslerH21,
author = {Guy Bresler and
Brice Huang},
title = {The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {298--309},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00038},
doi = {10.1109/FOCS52979.2021.00038},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BreslerH21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BukhSN21,
author = {Boris Bukh and
{Karthik {C. S.}} and
Bhargav Narayanan},
title = {Applications of Random Algebraic Constructions to Hardness of Approximation},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {237--244},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00032},
doi = {10.1109/FOCS52979.2021.00032},
timestamp = {Wed, 07 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BukhSN21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BurkeFT21,
author = {Kyle W. Burke and
Matthew T. Ferland and
Shang{-}Hua Teng},
title = {Winning the War by (Strategically) Losing Battles: Settling the Complexity
of Grundy-Values in Undirected Geography},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1217--1228},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00119},
doi = {10.1109/FOCS52979.2021.00119},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BurkeFT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CarmosinoKKO21,
author = {Marco Carmosino and
Valentine Kabanets and
Antonina Kolokolova and
Igor C. Oliveira},
title = {LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {770--780},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00080},
doi = {10.1109/FOCS52979.2021.00080},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/CarmosinoKKO21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CasteigtsRRZ21,
author = {Arnaud Casteigts and
Michael Raskin and
Malte Renken and
Viktor Zamaraev},
title = {Sharp Thresholds in Random Simple Temporal Graphs},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {319--326},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00040},
doi = {10.1109/FOCS52979.2021.00040},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/CasteigtsRRZ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Cen0NPSQ21,
author = {Ruoxu Cen and
Jason Li and
Danupon Nanongkai and
Debmalya Panigrahi and
Thatchaphol Saranurak and
Kent Quanrud},
title = {Minimum Cuts in Directed Graphs via Partial Sparsification},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1147--1158},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00113},
doi = {10.1109/FOCS52979.2021.00113},
timestamp = {Sun, 12 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Cen0NPSQ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChakrabartyCK21,
author = {Deeparnab Chakrabarty and
Yu Chen and
Sanjeev Khanna},
title = {A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular
Function Minimization},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {37--48},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00013},
doi = {10.1109/FOCS52979.2021.00013},
timestamp = {Thu, 07 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ChakrabartyCK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChattopadhyayG21,
author = {Eshan Chattopadhyay and
Jesse Goodman},
title = {Improved Extractors for Small-Space Sources},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {610--621},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00066},
doi = {10.1109/FOCS52979.2021.00066},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChattopadhyayG21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChattopadhyayGL21,
author = {Eshan Chattopadhyay and
Jesse Goodman and
Jyun{-}Jie Liao},
title = {Affine Extractors for Almost Logarithmic Entropy},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {622--633},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00067},
doi = {10.1109/FOCS52979.2021.00067},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChattopadhyayGL21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenCH021,
author = {Sitan Chen and
Jordan Cotler and
Hsin{-}Yuan Huang and
Jerry Li},
title = {Exponential Separations Between Learning With and Without Quantum
Memory},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {574--585},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00063},
doi = {10.1109/FOCS52979.2021.00063},
timestamp = {Sun, 12 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenCH021.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenFYZ21,
author = {Xiaoyu Chen and
Weiming Feng and
Yitong Yin and
Xinyuan Zhang},
title = {Rapid mixing of Glauber dynamics via spectral independence for all
degrees},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {137--148},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00022},
doi = {10.1109/FOCS52979.2021.00022},
timestamp = {Wed, 24 Aug 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ChenFYZ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenKM21,
author = {Sitan Chen and
Adam R. Klivans and
Raghu Meka},
title = {Learning Deep ReLU Networks Is Fixed-Parameter Tractable},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {696--707},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00073},
doi = {10.1109/FOCS52979.2021.00073},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenKM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenKMY21,
author = {Sitan Chen and
Frederic Koehler and
Ankur Moitra and
Morris Yau},
title = {Online and Distribution-Free Robustness: Regression and Contextual
Bandits with Huber Contamination},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {684--695},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00072},
doi = {10.1109/FOCS52979.2021.00072},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenKMY21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenLV21,
author = {Zongchen Chen and
Kuikui Liu and
Eric Vigoda},
title = {Spectral Independence via Stability and Applications to Holant-Type
Problems},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {149--160},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00023},
doi = {10.1109/FOCS52979.2021.00023},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenLV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenPW21,
author = {Li Chen and
Richard Peng and
Di Wang},
title = {2-norm Flow Diffusion in Near-Linear Time},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {540--549},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00060},
doi = {10.1109/FOCS52979.2021.00060},
timestamp = {Fri, 19 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ChenPW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CherapanamjeriN21,
author = {Yeshwanth Cherapanamjeri and
Jelani Nelson},
title = {Terminal Embeddings in Sublinear Time},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1209--1216},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00118},
doi = {10.1109/FOCS52979.2021.00118},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CherapanamjeriN21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChiaCLY21,
author = {Nai{-}Hui Chia and
Kai{-}Min Chung and
Qipeng Liu and
Takashi Yamakawa},
title = {On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant
Round},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {59--67},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00015},
doi = {10.1109/FOCS52979.2021.00015},
timestamp = {Fri, 30 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ChiaCLY21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChiesaMSZ21,
author = {Alessandro Chiesa and
Fermi Ma and
Nicholas Spooner and
Mark Zhandry},
title = {Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {49--58},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00014},
doi = {10.1109/FOCS52979.2021.00014},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChiesaMSZ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChouGSV21,
author = {Chi{-}Ning Chou and
Alexander Golovnev and
Madhu Sudan and
Santhoshini Velusamy},
title = {Approximability of all finite CSPs with linear sketches},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1197--1208},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00117},
doi = {10.1109/FOCS52979.2021.00117},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ChouGSV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChoudhuriJJ21,
author = {Arka Rai Choudhuri and
Abhishek Jain and
Zhengzhong Jin},
title = {SNARGs for {\textdollar}{\textbackslash}mathcal\{P\}{\textdollar}
from {LWE}},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {68--79},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00016},
doi = {10.1109/FOCS52979.2021.00016},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ChoudhuriJJ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CobleC21,
author = {Nolan J. Coble and
Matthew Coudron},
title = {Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local,
Shallow Quantum Circuits},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {598--609},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00065},
doi = {10.1109/FOCS52979.2021.00065},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/CobleC21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Cohen-Addad0KPT21,
author = {Vincent Cohen{-}Addad and
Debarati Das and
Evangelos Kipouridis and
Nikos Parotsidis and
Mikkel Thorup},
title = {Fitting Distances by Tree Metrics Minimizing the Total Error within
a Constant Factor},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {468--479},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00054},
doi = {10.1109/FOCS52979.2021.00054},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/Cohen-Addad0KPT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CzerwinskiO21,
author = {Wojciech Czerwinski and
Lukasz Orlikowski},
title = {Reachability in Vector Addition Systems is Ackermann-complete},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1229--1240},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00120},
doi = {10.1109/FOCS52979.2021.00120},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CzerwinskiO21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DalirrooyfardLW21,
author = {Mina Dalirrooyfard and
Ray Li and
Virginia Vassilevska Williams},
title = {Hardness of Approximate Diameter: Now for Undirected Graphs},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1021--1032},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00102},
doi = {10.1109/FOCS52979.2021.00102},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DalirrooyfardLW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DietrichW21,
author = {Heiko Dietrich and
James B. Wilson},
title = {Group isomorphism is nearly-linear time for most orders},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {457--467},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00053},
doi = {10.1109/FOCS52979.2021.00053},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/DietrichW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DingdNS21,
author = {Jingqiu Ding and
Tommaso d'Orsi and
Rajai Nasser and
David Steurer},
title = {Robust recovery for stochastic block models},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {387--394},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00046},
doi = {10.1109/FOCS52979.2021.00046},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DingdNS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DinurKK21,
author = {Itai Dinur and
Nathan Keller and
Ohad Klein},
title = {Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM
and k-XOR},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {80--91},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00017},
doi = {10.1109/FOCS52979.2021.00017},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DinurKK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DotyEGSUS21,
author = {David Doty and
Mahsa Eftekhari and
Leszek Gasieniec and
Eric E. Severson and
Przemyslaw Uznanski and
Grzegorz Stachowiak},
title = {A time and space optimal stable population protocol solving exact
majority},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1044--1055},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00104},
doi = {10.1109/FOCS52979.2021.00104},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/DotyEGSUS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DuttaD021,
author = {Pranjal Dutta and
Prateek Dwivedi and
Nitin Saxena},
title = {Demystifying the border of depth-3 algebraic circuits},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {92--103},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00018},
doi = {10.1109/FOCS52979.2021.00018},
timestamp = {Thu, 07 Dec 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/DuttaD021.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/DuttingEFK21,
author = {Paul D{\"{u}}tting and
Tomer Ezra and
Michal Feldman and
Thomas Kesselheim},
title = {Combinatorial Contracts},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {815--826},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00084},
doi = {10.1109/FOCS52979.2021.00084},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/DuttingEFK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/EfremenkoKPS21,
author = {Klim Efremenko and
Gillat Kol and
Dmitry Paramonov and
Raghuvansh R. Saxena},
title = {Tight Bounds for General Computation in Noisy Broadcast Networks},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {634--645},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00068},
doi = {10.1109/FOCS52979.2021.00068},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/EfremenkoKPS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FeldmanMT21,
author = {Vitaly Feldman and
Audra McMillan and
Kunal Talwar},
title = {Hiding Among the Clones: {A} Simple and Nearly Optimal Analysis of
Privacy Amplification by Shuffling},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {954--964},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00096},
doi = {10.1109/FOCS52979.2021.00096},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/FeldmanMT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FerberKS21,
author = {Asaf Ferber and
Matthew Kwan and
Lisa Sauermann},
title = {List-decodability with large radius for Reed-Solomon codes},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {720--726},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00075},
doi = {10.1109/FOCS52979.2021.00075},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/FerberKS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Filos-RatsikasH21,
author = {Aris Filos{-}Ratsikas and
Kristoffer Arnsfelt Hansen and
Kasper H{\o}gh and
Alexandros Hollender},
title = {FIXP-membership via Convex Optimization: Games, Cakes, and Markets},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {827--838},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00085},
doi = {10.1109/FOCS52979.2021.00085},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/Filos-RatsikasH21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Filtser21,
author = {Arnold Filtser},
title = {Hop-Constrained Metric Embeddings and their Applications},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {492--503},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00056},
doi = {10.1109/FOCS52979.2021.00056},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Filtser21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FioriniJWY21,
author = {Samuel Fiorini and
Gwena{\"{e}}l Joret and
Stefan Weltge and
Yelena Yuditsky},
title = {Integer programs with bounded subdeterminants and two nonzeros per
row},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {13--24},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00011},
doi = {10.1109/FOCS52979.2021.00011},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/FioriniJWY21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ForsterGLPSY21,
author = {Sebastian Forster and
Gramoz Goranci and
Yang P. Liu and
Richard Peng and
Xiaorui Sun and
Mingquan Ye},
title = {Minor Sparsifiers and the Distributed Laplacian Paradigm},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {989--999},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00099},
doi = {10.1109/FOCS52979.2021.00099},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ForsterGLPSY21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GaoHHNYZ21,
author = {Ruiquan Gao and
Zhongtian He and
Zhiyi Huang and
Zipei Nie and
Bijun Yuan and
Yan Zhong},
title = {Improved Online Correlated Selection},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1265--1276},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00123},
doi = {10.1109/FOCS52979.2021.00123},
timestamp = {Thu, 23 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GaoHHNYZ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GaoLP21,
author = {Yu Gao and
Yang P. Liu and
Richard Peng},
title = {Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {516--527},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00058},
doi = {10.1109/FOCS52979.2021.00058},
timestamp = {Fri, 14 Jul 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/GaoLP21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GhaffariK21,
author = {Mohsen Ghaffari and
Fabian Kuhn},
title = {Deterministic Distributed Vertex Coloring: Simpler, Faster, and without
Network Decomposition},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1009--1020},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00101},
doi = {10.1109/FOCS52979.2021.00101},
timestamp = {Mon, 23 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/GhaffariK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GuoLSTW21,
author = {Zeyu Guo and
Ray Li and
Chong Shangguan and
Itzhak Tamo and
Mary Wootters},
title = {Improved List-Decodability and List-Recoverability of Reed-Solomon
Codes via Tree Packings: [Extended Abstract]},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {708--719},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00074},
doi = {10.1109/FOCS52979.2021.00074},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/GuoLSTW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GuruswamiHL21,
author = {Venkatesan Guruswami and
Xiaoyu He and
Ray Li},
title = {The zero-rate threshold for adversarial bit-deletions is less than
1/2},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {727--738},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00076},
doi = {10.1109/FOCS52979.2021.00076},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GuruswamiHL21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HaghtalabRS21,
author = {Nika Haghtalab and
Tim Roughgarden and
Abhishek Shetty},
title = {Smoothed Analysis with Adaptive Adversaries},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {942--953},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00095},
doi = {10.1109/FOCS52979.2021.00095},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HaghtalabRS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HatamiHTT21,
author = {Pooya Hatami and
William M. Hoza and
Avishay Tal and
Roei Tell},
title = {Fooling Constant-Depth Threshold Circuits (Extended Abstract)},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {104--115},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00019},
doi = {10.1109/FOCS52979.2021.00019},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HatamiHTT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HiraharaN21,
author = {Shuichi Hirahara and
Mikito Nanashima},
title = {On Worst-Case Learning in Relativized Heuristica},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {751--758},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00078},
doi = {10.1109/FOCS52979.2021.00078},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HiraharaN21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ilango21,
author = {Rahul Ilango},
title = {The Minimum Formula Size Problem is {(ETH)} Hard},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {427--432},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00050},
doi = {10.1109/FOCS52979.2021.00050},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ilango21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JainPV21,
author = {Vishesh Jain and
Huy Tuan Pham and
Thuy{-}Duong Vuong},
title = {Towards the sampling Lov{\'{a}}sz Local Lemma},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {173--183},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00025},
doi = {10.1109/FOCS52979.2021.00025},
timestamp = {Tue, 16 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/JainPV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JiNV0Y21,
author = {Zhengfeng Ji and
Anand Natarajan and
Thomas Vidick and
John Wright and
Henry Yuen},
title = {Quantum soundness of testing tensor codes},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {586--597},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00064},
doi = {10.1109/FOCS52979.2021.00064},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JiNV0Y21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/JonesPRTX21,
author = {Chris Jones and
Aaron Potechin and
Goutham Rajendran and
Madhur Tulsiani and
Jeff Xu},
title = {Sum-of-Squares Lower Bounds for Sparse Independent Set},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {406--416},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00048},
doi = {10.1109/FOCS52979.2021.00048},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JonesPRTX21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Kallaugher21,
author = {John Kallaugher},
title = {A Quantum Advantage for a Natural Streaming Problem},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {897--908},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00091},
doi = {10.1109/FOCS52979.2021.00091},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Kallaugher21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KangKKMO21,
author = {Dong Yeap Kang and
Tom Kelly and
Daniela K{\"{u}}hn and
Abhishek Methuku and
Deryk Osthus},
title = {A proof of the Erd{\"{o}}s-Faber-Lov{\'{a}}sz conjecture:
Algorithmic aspects},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1080--1089},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00107},
doi = {10.1109/FOCS52979.2021.00107},
timestamp = {Tue, 26 Mar 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KangKKMO21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KapralovKTY21,
author = {Michael Kapralov and
Robert Krauthgamer and
Jakab Tardos and
Yuichi Yoshida},
title = {Spectral Hypergraph Sparsifiers of Nearly Linear Size},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1159--1170},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00114},
doi = {10.1109/FOCS52979.2021.00114},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/KapralovKTY21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KawarabayashiS21,
author = {Ken{-}ichi Kawarabayashi and
Anastasios Sidiropoulos},
title = {Embeddings of Planar Quasimetrics into Directed {\(\mathscr{l}\)}1
and Polylogarithmic Approximation for Directed Sparsest-Cut},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {480--491},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00055},
doi = {10.1109/FOCS52979.2021.00055},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KawarabayashiS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KelnerKMR21,
author = {Jonathan A. Kelner and
Frederic Koehler and
Raghu Meka and
Dhruv Rohatgi},
title = {On the Power of Preconditioning in Sparse Linear Regression},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {550--561},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00061},
doi = {10.1109/FOCS52979.2021.00061},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KelnerKMR21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Kisfaludi-BakNW21,
author = {S{\'{a}}ndor Kisfaludi{-}Bak and
Jesper Nederlof and
Karol Wegrzycki},
title = {A Gap-ETH-Tight Approximation Scheme for Euclidean {TSP}},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {351--362},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00043},
doi = {10.1109/FOCS52979.2021.00043},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/Kisfaludi-BakNW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KociumakaPS21,
author = {Tomasz Kociumaka and
Ely Porat and
Tatiana Starikovskaya},
title = {Small-space and streaming pattern matching with {\textdollar}k{\textdollar}
edits},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {885--896},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00090},
doi = {10.1109/FOCS52979.2021.00090},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/KociumakaPS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KondoMM21,
author = {Yasuhiro Kondo and
Ryuhei Mori and
Ramis Movassagh},
title = {Quantum supremacy and hardness of estimating output probabilities
of quantum circuits},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1296--1307},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00126},
doi = {10.1109/FOCS52979.2021.00126},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KondoMM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Korhonen21,
author = {Tuukka Korhonen},
title = {A Single-Exponential Time 2-Approximation Algorithm for Treewidth},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {184--192},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00026},
doi = {10.1109/FOCS52979.2021.00026},
timestamp = {Thu, 23 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/Korhonen21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Korten21,
author = {Oliver Korten},
title = {The Hardest Explicit Construction},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {433--444},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00051},
doi = {10.1109/FOCS52979.2021.00051},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Korten21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KuszmaulN21,
author = {William Kuszmaul and
Shyam Narayanan},
title = {Stochastic and Worst-Case Generalized Sorting Revisited},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1056--1067},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00105},
doi = {10.1109/FOCS52979.2021.00105},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KuszmaulN21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LeW21,
author = {Hung Le and
Christian Wulff{-}Nilsen},
title = {Optimal Approximate Distance Oracle for Planar Graphs},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {363--374},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00044},
doi = {10.1109/FOCS52979.2021.00044},
timestamp = {Sun, 05 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/LeW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LecomteT21,
author = {Victor Lecomte and
Li{-}Yang Tan},
title = {Sharper bounds on the Fourier concentration of DNFs},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {930--941},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00094},
doi = {10.1109/FOCS52979.2021.00094},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LecomteT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LeeV21,
author = {Jasper C. H. Lee and
Paul Valiant},
title = {Optimal Sub-Gaussian Mean Estimation in {\textdollar}{\textbackslash}mathbb\{R\}{\textdollar}},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {672--683},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00071},
doi = {10.1109/FOCS52979.2021.00071},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LeeV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Leroux21,
author = {J{\'{e}}r{\^{o}}me Leroux},
title = {The Reachability Problem for Petri Nets is Not Primitive Recursive},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1241--1252},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00121},
doi = {10.1109/FOCS52979.2021.00121},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Leroux21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LiV21,
author = {Wenzheng Li and
Jan Vondr{\'{a}}k},
title = {A constant-factor approximation algorithm for Nash Social Welfare
with submodular valuations},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {25--36},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00012},
doi = {10.1109/FOCS52979.2021.00012},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LiV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LiWY21,
author = {Yuanzhi Li and
Ruosong Wang and
Lin F. Yang},
title = {Settling the Horizon-Dependence of Sample Complexity in Reinforcement
Learning},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {965--976},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00097},
doi = {10.1109/FOCS52979.2021.00097},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/LiWY21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Limaye0T21,
author = {Nutan Limaye and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
title = {Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {804--814},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00083},
doi = {10.1109/FOCS52979.2021.00083},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Limaye0T21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LiuMR21,
author = {Siqi Liu and
Sidhanth Mohanty and
Prasad Raghavendra},
title = {On statistical inference when fixed points of belief propagation are
unstable},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {395--405},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00047},
doi = {10.1109/FOCS52979.2021.00047},
timestamp = {Fri, 12 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/LiuMR21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Mao21,
author = {Xiao Mao},
title = {Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {792--803},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00082},
doi = {10.1109/FOCS52979.2021.00082},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Mao21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/MiltzowS21,
author = {Tillmann Miltzow and
Reinier F. Schmiermann},
title = {On Classifying Continuous Constraint Satisfaction problems},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {781--791},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00081},
doi = {10.1109/FOCS52979.2021.00081},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/MiltzowS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Mitchell21,
author = {Joseph S. B. Mitchell},
title = {Approximating Maximum Independent Set for Rectangles in the Plane},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {339--350},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00042},
doi = {10.1109/FOCS52979.2021.00042},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Mitchell21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Moroz21,
author = {Guillaume Moroz},
title = {New data structure for univariate polynomial approximation and applications
to root isolation, numerical multipoint evaluation, and other problems},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1090--1099},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00108},
doi = {10.1109/FOCS52979.2021.00108},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Moroz21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/NamSS21,
author = {Danny Nam and
Allan Sly and
Youngtak Sohn},
title = {One-step replica symmetry breaking of random regular {NAE-SAT}},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {310--318},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00039},
doi = {10.1109/FOCS52979.2021.00039},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/NamSS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/OlverSK21,
author = {Neil Olver and
Leon Sering and
Laura Vargas Koch},
title = {Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {851--860},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00087},
doi = {10.1109/FOCS52979.2021.00087},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/OlverSK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/PalmerP21,
author = {Cory Palmer and
D{\"{o}}m{\"{o}}t{\"{o}}r P{\'{a}}lv{\"{o}}lgyi},
title = {At most 3.55\({}^{\mbox{n}}\) stable matchings},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {217--227},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00029},
doi = {10.1109/FOCS52979.2021.00029},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/PalmerP21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/PitassiRT21,
author = {Toniann Pitassi and
Prasanna Ramakrishnan and
Li{-}Yang Tan},
title = {Tradeoffs for small-depth Frege proofs},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {445--456},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00052},
doi = {10.1109/FOCS52979.2021.00052},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/PitassiRT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/RobereZ21,
author = {Robert Robere and
Jeroen Zuiddam},
title = {Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic
Algorithms},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {759--769},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00079},
doi = {10.1109/FOCS52979.2021.00079},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/RobereZ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Sandeep21,
author = {Sai Sandeep},
title = {Almost Optimal Inapproximability of Multidimensional Packing Problems},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {245--256},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00033},
doi = {10.1109/FOCS52979.2021.00033},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Sandeep21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Scheder21,
author = {Dominik Scheder},
title = {{PPSZ} is better than you think},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {205--216},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00028},
doi = {10.1109/FOCS52979.2021.00028},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Scheder21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/TraubZ21,
author = {Vera Traub and
Rico Zenklusen},
title = {A Better-Than-2 Approximation for Weighted Tree Augmentation},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1--12},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00010},
doi = {10.1109/FOCS52979.2021.00010},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/TraubZ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Vishnoi21,
author = {Nisheeth K. Vishnoi},
title = {{FOCS} 2021 Preface},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {xvii},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00005},
doi = {10.1109/FOCS52979.2021.00005},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Vishnoi21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Wesolowski21,
author = {Benjamin Wesolowski},
title = {The supersingular isogeny path and endomorphism ring problems are
equivalent},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1100--1111},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00109},
doi = {10.1109/FOCS52979.2021.00109},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Wesolowski21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/WoodruffZ21,
author = {David P. Woodruff and
Samson Zhou},
title = {Tight Bounds for Adversarially Robust Streams and Sliding Windows
via Difference Estimators},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {1183--1196},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00116},
doi = {10.1109/FOCS52979.2021.00116},
timestamp = {Wed, 09 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/WoodruffZ21.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-05-22 11:00 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:
