FOCS A*

128 papers

YearTitle / Authors
20202D Generalization of Fractional Cascading on Axis-aligned Planar Subdivisions.
Peyman Afshani, Pingan Cheng
202061st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020
Sandy Irani
2020A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak
2020A Dichotomy for Real Boolean Holant Problems.
Shuai Shao, Jin-Yi Cai
2020A Faster Interior Point Method for Semidefinite Programming.
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, Zhao Song
2020A New Minimax Theorem for Randomized Algorithms (Extended Abstract).
Shalev Ben-David, Eric Blais
2020A Parameterized Approximation Scheme for Min $k$-Cut.
Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
2020A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract.
Shalev Ben-David, Eric Blais
2020A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip.
Iftach Haitner, Yonatan Karidi-Heller
2020A constant rate non-malleable code in the split-state model.
Divesh Aggarwal, Maciej Obremski
2020AdWords in a Panorama.
Zhiyi Huang, Qiankun Zhang, Yuhao Zhang
2020Adjacency Labelling for Planar Graphs (and Beyond).
Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, Pat Morin
2020Algorithms and Hardness for Linear Algebra on Geometric Graphs.
Josh Alman, Timothy Chu, Aaron Schild, Zhao Song
2020Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization.
Lijie Chen, Xin Lyu, R. Ryan Williams
2020An Adaptive Step Toward the Multiphase Conjecture.
Young Kun-Ko, Omri Weinstein
2020An Equivalence Between Private Classification and Online Prediction.
Mark Bun, Roi Livni, Shay Moran
2020An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature.
Andrew Drucker
2020An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions.
Paul Dütting, Thomas Kesselheim, Brendan Lucier
2020Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations.
Ariel Kulik, Hadas Shachnai
2020Approximation Algorithms for Stochastic Minimum-Norm Combinatorial Optimization.
Sharat Ibrahimpur, Chaitanya Swamy
2020Benchmark Design and Prior-independent Optimization.
Jason D. Hartline, Aleck C. Johnsen, Yingkai Li
2020Beyond Tree Embeddings - a Deterministic Framework for Network Design with Deadlines or Delay.
Yossi Azar, Noam Touitou
2020Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$.
Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
2020Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2020Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity.
Shuichi Hirahara
2020Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs.
Kyriakos Axiotis, Aleksander Madry, Adrian Vladu
2020Coded trace reconstruction in a constant number of traces.
Joshua Brakensiek, Ray Li, Bruce Spang
2020Collaborative Top Distribution Identifications with Limited Interaction (Extended Abstract).
Nikolai Karpov, Qin Zhang, Yuan Zhou
2020Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time.
Mahdi Cheraghchi, Vasileios Nakos
2020Communication complexity of Nash equilibrium in potential games (extended abstract).
Yakov Babichenko, Aviad Rubinstein
2020Constant Depth Formula and Partial Function Versions of MCSP are Hard.
Rahul Ilango
2020Coordinate Methods for Matrix Games.
Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian
2020Correlated Pseudorandom Functions from Variable-Density LPN.
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Scholl
2020Counting Small Induced Subgraphs Satisfying Monotone Properties.
Marc Roth, Johannes Schmitt, Philip Wellnitz
2020Cut-Equivalent Trees are Optimal for Min-Cut Queries.
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
2020Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders.
Shai Evra, Tali Kaufman, Gilles Zémor
2020Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing.
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2020Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization.
Yi-Jun Chang, Thatchaphol Saranurak
2020Deterministic Min-cut in Poly-logarithmic Max-flows.
Jason Li, Debmalya Panigrahi
2020Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes.
Zvika Brakerski, Yael Tauman Kalai, Raghuvansh R. Saxena
2020Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs.
Jin-Yi Cai, Artem Govorov
2020Distributed Lower Bounds for Ruling Sets.
Alkida Balliu, Sebastian Brandt, Dennis Olivetti
2020Edge-Weighted Online Bipartite Matching.
Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, Morteza Zadimoghaddam
2020Edit Distance in Near-Linear Time: it's a Constant Factor.
Alexandr Andoni, Negev Shekel Nosatzki
2020Entanglement is Necessary for Optimal Quantum Property Testing.
Sébastien Bubeck, Sitan Chen, Jerry Li
2020Explicit near-fully X-Ramanujan graphs.
Ryan O'Donnell, Xinyu Wu
2020Extractors and Secret Sharing Against Bounded Collusion Protocols.
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, David Zuckerman
2020Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.
Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, Thatchaphol Saranurak
2020Faster Approximate Pattern Matching: A Unified Approach.
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
2020Framework for ER-Completeness of Two-Dimensional Packing Problems.
Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth
2020Fully Online Matching II: Beating Ranking and Water-filling.
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang
2020Fully-Dynamic Submodular Cover with Bounded Recourse.
Anupam Gupta, Roie Levin
2020High-precision Estimation of Random Walks in Small Space.
AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, Salil P. Vadhan
2020Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time.
Karthekeyan Chandrasekaran, Chandra Chekuri
2020Independent Set on $\mathrm{P}_{k}$-Free Graphs in Quasi-Polynomial Time.
Peter Gartland, Daniel Lokshtanov
2020Is it Easier to Prove Theorems that are Guaranteed to be True?
Rafael Pass, Muthuramakrishnan Venkitasubramaniam
2020Isomorphism Testing for Graphs Excluding Small Minors.
Martin Grohe, Daniel Wiebking, Daniel Neuen
2020Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases.
Nima Anari, Michal Derezinski
2020KRW Composition Theorems via Lifting.
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere
2020Kernel Density Estimation through Density Constrained Near Neighbor Search.
Moses Charikar, Michael Kapralov, Navid Nouri, Paris Siminelakis
2020LDPC Codes Achieve List Decoding Capacity.
Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters
2020Lazy Search Trees.
Bryce Sandlund, Sebastian Wild
2020Learning sums of powers of low-degree polynomials in the non-degenerate case.
Ankit Garg, Neeraj Kayal, Chandan Saha
2020Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals
2020List Decodable Mean Estimation in Nearly Linear Time.
Yeshwanth Cherapanamjeri, Sidhanth Mohanty, Morris Yau
2020Local Proofs Approaching the Witness Length [Extended Abstract].
Noga Ron-Zewi, Ron D. Rothblum
2020Low-Degree Hardness of Random Optimization Problems.
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
2020Maximizing Determinants under Matroid Constraints.
Vivek Madan, Aleksandar Nikolov, Mohit Singh, Uthaipon Tantipongpipat
2020Mechanisms for a No-Regret Agent: Beyond the Common Prior.
Modibo K. Camara, Jason D. Hartline, Aleck C. Johnsen
2020Monochromatic Triangles, Triangle Listing and APSP.
Virginia Vassilevska Williams, Yinzhan Xu
2020Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems.
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
2020Near Optimal Linear Algebra in the Online and Sliding Window Models.
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou
2020Near-Optimal Decremental SSSP in Dense Weighted Digraphs.
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms.
Sepehr Assadi, Ran Raz
2020Near-linear Size Hypergraph Cut Sparsifiers.
Yu Chen, Sanjeev Khanna, Ansh Nagda
2020Nearly Optimal Pseudorandomness From Hardness.
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
2020Network Coding Gaps for Completion Times of Multiple Unicasts.
Bernhard Haeupler, David Wajc, Goran Zuzic
2020New Techniques for Proving Fine-Grained Average-Case Hardness.
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
2020On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract.
Lijie Chen, Ron D. Rothblum, Roei Tell, Eylon Yogev
2020On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs.
Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
2020On One-way Functions and Kolmogorov Complexity.
Yanyi Liu, Rafael Pass
2020On the Existence of Algebraically Natural Proofs.
Prerona Chatterjee, Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, Anamay Tengse
2020Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat.
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
2020Optimal anytime regret for two experts.
Nicholas J. A. Harvey, Christopher Liaw, Edwin A. Perkins, Sikander Randhawa
2020Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures.
Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, Pravesh K. Kothari
2020Pandora's Box with Correlations: Learning and Approximation.
Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, Ruimin Zhang
2020Point Location and Active Learning: Learning Halfspaces Almost Optimally.
Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
2020Polynomial Data Structure Lower Bounds in the Group Model.
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
2020Proximity Gaps for Reed-Solomon Codes.
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf
2020Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time.
Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, Nikhil Srivastava
2020QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge.
Anne Broadbent, Alex B. Grilo
2020Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving.
Simon Apers, Ronald de Wolf
2020Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs.
Laura Mancinska, David E. Roberson
2020Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction.
Zongchen Chen, Kuikui Liu, Eric Vigoda
2020Resolution of the Burrows-Wheeler Transform Conjecture.
Dominik Kempa, Tomasz Kociumaka
2020Resolving the Optimal Metric Distortion Conjecture.
Vasilis Gkatzelis, Daniel Halpern, Nisarg Shah
2020Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers.
Daniel Dadush, Bento Natura, László A. Végh
2020Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs.
Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal
2020Robust and Sample Optimal Algorithms for PSD Low Rank Approximation.
Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
2020Sample-efficient learning of quantum many-body systems.
Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi Soleimanifar
2020Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay.
Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa, Zoya Svitkina, Aravindan Vijayaraghavan
2020Scheduling with Communication Delays via LP Hierarchies and Clustering.
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang
2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models.
Ilias Diakonikolas, Daniel M. Kane
2020Smoothed Complexity of 2-player Nash Equilibria.
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
2020Smoothing the gap between NP and ER.
Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow
2020Sparse PCA: Algorithms, Adversarial Perturbations and Certificates.
Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer
2020Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model.
Nima Anari, Kuikui Liu, Shayan Oveis Gharan
2020Stochastic Weighted Matching: (Stochastic Weighted Matching: (1-ε) Approximation -\varepsilon$) Approximation.
Soheil Behnezhad, Mahsa Derakhshan
2020Subexponential LPs Approximate Max-Cut.
Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
2020Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.
Tomasz Kociumaka, Barna Saha
2020Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search.
Thomas D. Ahle, Jakob Bæk Tejs Knudsen
2020Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes.
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran
2020Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties.
Visu Makam, Avi Wigderson
2020Symmetries, Graph Properties, and Quantum Speedups.
Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
2020Testing Positive Semi-Definiteness via Random Submatrices.
Ainesh Bakshi, Nadiia Chepurko, Rajesh Jayaram
2020Testing linear-invariant properties.
Jonathan Tidor, Yufei Zhao
2020The Coin Problem with Applications to Data Streams.
Mark Braverman, Sumegha Garg, David P. Woodruff
2020The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency.
Benny Applebaum, Eliran Kachlon, Arpita Patra
2020The complexity of approximating averages on bounded-degree graphs.
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
2020Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise.
Noah Shutty, Mary Wootters, Patrick Hayden
2020Tight Quantum Time-Space Tradeoffs for Function Inversion.
Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian
2020Towards Better Approximation of Graph Crossing Number.
Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan
2020Towards Optimal Separations between Quantum and Randomized Query Complexities.
Avishay Tal
2020Towards a Proof of the Fourier-Entropy Conjecture?
Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra
2020Tree-depth and the Formula Complexity of Subgraph Isomorphism.
Deepanshu Kush, Benjamin Rossman
2020Twin-width I: tractable FO model checking.
Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
2020Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound.
Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani
2020Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time.
Tarun Kathuria, Yang P. Liu, Aaron Sidford