default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID61st FOCS 2020: Durham, NC, USA
- Sandy Irani:
61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020. IEEE 2020, ISBN 978-1-7281-9621-3
Session 1A
- Lijie Chen, Xin Lyu, R. Ryan Williams
:
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. 1-12 - Lijie Chen, Ron D. Rothblum, Roei Tell, Eylon Yogev:
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract. 13-23 - Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals:
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. 24-30 - Deepanshu Kush, Benjamin Rossman:
Tree-depth and the Formula Complexity of Subgraph Isomorphism. 31-42 - Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. 43-49 - Shuichi Hirahara:
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity. 50-60
Session 1B
- Yu Chen, Sanjeev Khanna, Ansh Nagda:
Near-linear Size Hypergraph Cut Sparsifiers. 61-72 - Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan:
Towards Better Approximation of Graph Crossing Number. 73-84 - Jason Li, Debmalya Panigrahi:
Deterministic Min-cut in Poly-logarithmic Max-flows. 85-92 - Kyriakos Axiotis, Aleksander Madry, Adrian Vladu:
Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs. 93-104 - Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Cut-Equivalent Trees are Optimal for Min-Cut Queries. 105-118 - Tarun Kathuria, Yang P. Liu, Aaron Sidford:
Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time. 119-130
Session 1C
- David Gamarnik, Aukosh Jagannath, Alexander S. Wein:
Low-Degree Hardness of Random Optimization Problems. 131-140 - Yeshwanth Cherapanamjeri, Sidhanth Mohanty, Morris Yau:
List Decodable Mean Estimation in Nearly Linear Time. 141-148 - Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, Pravesh K. Kothari:
Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures. 149-159 - Nikolai Karpov, Qin Zhang, Yuan Zhou:
Collaborative Top Distribution Identifications with Limited Interaction (Extended Abstract). 160-171 - Moses Charikar, Michael Kapralov, Navid Nouri, Paris Siminelakis:
Kernel Density Estimation through Density Constrained Near Neighbor Search. 172-183 - Ilias Diakonikolas, Daniel M. Kane:
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. 184-195
Session 2A
- Anne Broadbent, Alex B. Grilo:
QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge. 196-205 - Noah Shutty, Mary Wootters, Patrick Hayden:
Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise. 206-217 - Shai Evra, Tali Kaufman, Gilles Zémor:
Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders. 218-227 - Avishay Tal:
Towards Optimal Separations between Quantum and Randomized Query Complexities. 228-239 - Shalev Ben-David, Eric Blais:
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract. 240-246 - Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra:
Towards a Proof of the Fourier-Entropy Conjecture? 247-258
Session 2B
- Modibo K. Camara, Jason D. Hartline, Aleck C. Johnsen:
Mechanisms for a No-Regret Agent: Beyond the Common Prior. 259-270 - Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein:
Smoothed Complexity of 2-player Nash Equilibria. 271-282 - Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian:
Coordinate Methods for Matrix Games. 283-293 - Jason D. Hartline, Aleck C. Johnsen, Yingkai Li:
Benchmark Design and Prior-independent Optimization. 294-305 - Paul Dütting, Thomas Kesselheim, Brendan Lucier:
An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions. 306-317
Session 2C
- Mark Braverman, Sumegha Garg, David P. Woodruff:
The Coin Problem with Applications to Data Streams. 318-329 - Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy:
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat. 330-341 - Sepehr Assadi, Ran Raz:
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. 342-353 - Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu:
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. 354-364 - Alkida Balliu, Sebastian Brandt, Dennis Olivetti:
Distributed Lower Bounds for Ruling Sets. 365-376 - Yi-Jun Chang, Thatchaphol Saranurak:
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization. 377-388
Session 3: Plenary Session
- Mark Bun, Roi Livni, Shay Moran:
An Equivalence Between Private Classification and Online Prediction. 389-402 - Shalev Ben-David, Eric Blais:
A New Minimax Theorem for Randomized Algorithms (Extended Abstract). 403-411 - Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, Morteza Zadimoghaddam:
Edge-Weighted Online Bipartite Matching. 412-423 - Rahul Ilango:
Constant Depth Formula and Partial Function Versions of MCSP are Hard. 424-433
Session 4A
- Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani:
Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound. 434-445 - Zvika Brakerski, Yael Tauman Kalai, Raghuvansh R. Saxena:
Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes. 446-457 - Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters:
LDPC Codes Achieve List Decoding Capacity. 458-469 - Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena:
Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$. 470-481 - Joshua Brakensiek, Ray Li, Bruce Spang:
Coded trace reconstruction in a constant number of traces. 482-493 - Bernhard Haeupler, David Wajc, Goran Zuzic:
Network Coding Gaps for Completion Times of Multiple Unicasts. 494-505
Session 4B
- Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff:
Robust and Sample Optimal Algorithms for PSD Low Rank Approximation. 506-516 - Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou:
Near Optimal Linear Algebra in the Online and Sliding Window Models. 517-528 - Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, Nikhil Srivastava:
Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time. 529-540 - Josh Alman, Timothy Chu, Aaron Schild, Zhao Song:
Algorithms and Hardness for Linear Algebra on Geometric Graphs. 541-552 - Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer:
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. 553-564 - Vivek Madan, Aleksandar Nikolov, Mohit Singh, Uthaipon Tantipongpipat:
Maximizing Determinants under Matroid Constraints. 565-576
Session 4C
- Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, Pat Morin:
Adjacency Labelling for Planar Graphs (and Beyond). 577-588 - Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le:
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. 589-600 - Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-width I: tractable FO model checking. 601-612 - Peter Gartland, Daniel Lokshtanov:
Independent Set on $\mathrm{P}_{k}$-Free Graphs in Quasi-Polynomial Time. 613-624 - Martin Grohe, Daniel Wiebking, Daniel Neuen:
Isomorphism Testing for Graphs Excluding Small Minors. 625-636
Session 5A
- Simon Apers, Ronald de Wolf:
Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving. 637-648 - Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang:
Symmetries, Graph Properties, and Quantum Speedups. 649-660 - Laura Mancinska, David E. Roberson:
Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. 661-672 - Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian:
Tight Quantum Time-Space Tradeoffs for Function Inversion. 673-684 - Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi Soleimanifar:
Sample-efficient learning of quantum many-body systems. 685-691 - Sébastien Bubeck, Sitan Chen, Jerry Li:
Entanglement is Necessary for Optimal Quantum Property Testing. 692-703
Session 5B
- Bryce Sandlund, Sebastian Wild:
Lazy Search Trees. 704-715 - Peyman Afshani, Pingan Cheng:
2D Generalization of Fractional Cascading on Axis-aligned Planar Subdivisions. 716-727 - Thomas D. Ahle, Jakob Bæk Tejs Knudsen:
Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search. 728-739 - Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein:
Polynomial Data Structure Lower Bounds in the Group Model. 740-751 - Young Kun-Ko, Omri Weinstein:
An Adaptive Step Toward the Multiphase Conjecture. 752-761 - Ariel Kulik, Hadas Shachnai:
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations. 762-773
Session 5C
- Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams:
New Techniques for Proving Fine-Grained Average-Case Hardness. 774-785 - Virginia Vassilevska Williams, Yinzhan Xu:
Monochromatic Triangles, Triangle Listing and APSP. 786-797 - Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan:
A Parameterized Approximation Scheme for Min $k$-Cut. 798-809 - Karthekeyan Chandrasekaran, Chandra Chekuri:
Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time. 810-821 - Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang:
Scheduling with Communication Delays via LP Hierarchies and Clustering. 822-833 - Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa, Zoya Svitkina, Aravindan Vijayaraghavan:
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay. 834-845
Session 6A
- Noga Ron-Zewi, Ron D. Rothblum:
Local Proofs Approaching the Witness Length [Extended Abstract]. 846-857 - Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal:
Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs. 858-869 - Prerona Chatterjee, Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, Anamay Tengse:
On the Existence of Algebraically Natural Proofs. 870-880 - Visu Makam, Avi Wigderson:
Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties. 881-888 - Ankit Garg, Neeraj Kayal, Chandan Saha:
Learning sums of powers of low-degree polynomials in the non-degenerate case. 889-899 - Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf:
Proximity Gaps for Reed-Solomon Codes. 900-909
Session 6B
- Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, Zhao Song:
A Faster Interior Point Method for Semidefinite Programming. 910-918 - Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang:
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. 919-930 - Daniel Dadush, Bento Natura, László A. Végh:
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers. 931-942 - Samuel B. Hopkins, Tselil Schramm, Luca Trevisan:
Subexponential LPs Approximate Max-Cut. 943-953 - Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran:
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes. 954-965 - Sharat Ibrahimpur, Chaitanya Swamy:
Approximation Algorithms for Stochastic Minimum-Norm Combinatorial Optimization. 966-977
Session 6C
- Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz:
Faster Approximate Pattern Matching: A Unified Approach. 978-989 - Alexandr Andoni, Negev Shekel Nosatzki:
Edit Distance in Near-Linear Time: it's a Constant Factor. 990-1001 - Dominik Kempa, Tomasz Kociumaka:
Resolution of the Burrows-Wheeler Transform Conjecture. 1002-1013 - Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth:
Framework for ER-Completeness of Two-Dimensional Packing Problems. 1014-1021 - Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow:
Smoothing the gap between NP and ER. 1022-1033 - Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan:
Point Location and Active Learning: Learning Halfspaces Almost Optimally. 1034-1044
Session 7A
- Ryan O'Donnell, Xinyu Wu:
Explicit near-fully X-Ramanujan graphs. 1045-1056 - Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Nearly Optimal Pseudorandomness From Hardness. 1057-1068 - Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Scholl:
Correlated Pseudorandom Functions from Variable-Density LPN. 1069-1080 - Andrew Drucker:
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature. 1081-1090 - Shuai Shao, Jin-Yi Cai:
A Dichotomy for Real Boolean Holant Problems. 1091-1102 - Jin-Yi Cai, Artem Govorov:
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs. 1103-1111
Session 7B
- Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen:
Near-Optimal Decremental SSSP in Dense Weighted Digraphs. 1112-1122 - Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak:
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. 1123-1134 - Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, Thatchaphol Saranurak:
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers. 1135-1146 - Anupam Gupta, Roie Levin:
Fully-Dynamic Submodular Cover with Bounded Recourse. 1147-1157 - Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak:
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. 1158-1167
Session 7C
- Tomasz Kociumaka, Barna Saha:
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance. 1168-1179 - Jonathan Tidor, Yufei Zhao:
Testing linear-invariant properties. 1180-1190 - Ainesh Bakshi, Nadiia Chepurko, Rajesh Jayaram:
Testing Positive Semi-Definiteness via Random Submatrices. 1191-1202 - Mahdi Cheraghchi, Vasileios Nakos:
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time. 1203-1213 - Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, Ruimin Zhang:
Pandora's Box with Correlations: Learning and Approximation. 1214-1225
Session 8A
- Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, David Zuckerman:
Extractors and Secret Sharing Against Bounded Collusion Protocols. 1226-1242 - Yanyi Liu, Rafael Pass:
On One-way Functions and Kolmogorov Complexity. 1243-1254 - Rafael Pass, Muthuramakrishnan Venkitasubramaniam:
Is it Easier to Prove Theorems that are Guaranteed to be True? 1255-1267 - Iftach Haitner, Yonatan Karidi-Heller:
A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip. 1268-1276 - Benny Applebaum, Eliran Kachlon, Arpita Patra:
The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency. 1277-1284 - Divesh Aggarwal, Maciej Obremski:
A constant rate non-malleable code in the split-state model. 1285-1294
Session 8B
- AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, Salil P. Vadhan:
High-precision Estimation of Random Walks in Small Space. 1295-1306 - Zongchen Chen, Kuikui Liu, Eric Vigoda:
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. 1307-1318 - Nima Anari, Kuikui Liu, Shayan Oveis Gharan:
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. 1319-1330 - Nima Anari, Michal Derezinski:
Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases. 1331-1344 - Andreas Galanis, Daniel Stefankovic, Eric Vigoda:
The complexity of approximating averages on bounded-degree graphs. 1345-1355 - Marc Roth, Johannes Schmitt, Philip Wellnitz:
Counting Small Induced Subgraphs Satisfying Monotone Properties. 1356-1367
Session 8C
- Yossi Azar, Noam Touitou:
Beyond Tree Embeddings - a Deterministic Framework for Network Design with Deadlines or Delay. 1368-1379 - Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang:
Fully Online Matching II: Beating Ranking and Water-filling. 1380-1391 - Soheil Behnezhad, Mahsa Derakhshan:
Stochastic Weighted Matching: (Stochastic Weighted Matching: (1-ε) Approximation -\varepsilon$) Approximation. 1392-1403 - Nicholas J. A. Harvey, Christopher Liaw, Edwin A. Perkins, Sikander Randhawa:
Optimal anytime regret for two experts. 1404-1415 - Zhiyi Huang, Qiankun Zhang, Yuhao Zhang:
AdWords in a Panorama. 1416-1426 - Vasilis Gkatzelis, Daniel Halpern, Nisarg Shah:
Resolving the Optimal Metric Distortion Conjecture. 1427-1438 - Yakov Babichenko, Aviad Rubinstein:
Communication complexity of Nash equilibrium in potential games (extended abstract). 1439-1445
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-04 00:40 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
