default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID58th FOCS 2017: Berkeley, CA, USA
- Chris Umans:
58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. IEEE Computer Society 2017, ISBN 978-1-5386-3464-6
Session 1A
- Mark Bun
, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. 1-12 - Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz:
On the Quantitative Hardness of CVP. 13-24 - Amir Abboud, Aviad Rubinstein, R. Ryan Williams:
Distributed PCP Theorems for Hardness of Approximation in P. 25-36 - Danny Nguyen, Igor Pak:
Short Presburger Arithmetic Is Hard. 37-48
Session 1B
- Vincent Cohen-Addad, Chris Schwiegelshohn:
On the Local Structure of Stable Clustering Instances. 49-60 - Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, Justin Ward:
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms. 61-72 - Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. 73-84 - Oded Regev, Aravindan Vijayaraghavan:
On Learning Mixtures of Well-Separated Gaussians. 85-96
Session 2A
- Johan Håstad:
On Small-Depth Frege Proofs for Tseitin for Grids. 97-108 - Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere:
Random Θ(log n)-CNFs Are Hard for Cutting Planes. 109-120 - Pavel Hrubes, Pavel Pudlák:
Random Formulas, Monotone Circuits, and Interpolation. 121-131 - Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. 132-143 - Mark Braverman, Rotem Oshman:
A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. 144-155
Session 2B
- Yi-Jun Chang, Seth Pettie:
A Time Hierarchy Theorem for the LOCAL Model. 156-167 - Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak:
Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n5/4) Rounds. 168-179 - Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn:
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching. 180-191 - Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. 192-203
Session 3A
- Brett Hemenway, Noga Ron-Zewi, Mary Wootters:
Local List Recovery of High-Rate Tensor Codes & Applications. 204-215 - Itzhak Tamo, Min Ye, Alexander Barg:
Optimal Repair of Reed-Solomon Codes: Achieving the Cut-Set Bound. 216-227 - Yuval Peres, Alex Zhai:
Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice. 228-239 - Alexander A. Sherstov, Pei Wu:
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. 240-251 - Daniel Kane, Shachar Lovett, Sankeerth Rao:
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. 252-259
Session 3B
- Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, Andreas Wiese:
Approximating Geometric Knapsack via L-Packings. 260-271 - Mark de Berg:
Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments. 272-282 - Shi Li:
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. 283-294 - Barna Saha:
Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach. 295-306 - Karl Bringmann, Allan Grønlund, Kasper Green Larsen:
A Dichotomy for Regular Expression Membership Testing. 307-318
Session 4
- Andrei A. Bulatov:
A Dichotomy Theorem for Nonuniform CSPs. 319-330 - Dmitriy Zhuk:
A Proof of CSP Dichotomy Conjecture. 331-342
Session 5A
- Adam R. Klivans, Raghu Meka:
Learning Graphical Models Using Multiplicative Weights. 343-354 - Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang:
Active Classification with Comparison Queries. 355-366 - Leslie G. Valiant:
Capacity of Neural Networks for Lifelong Learning of Composable Tasks. 367-378 - Samuel B. Hopkins, David Steurer:
Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. 379-390 - Daniel Kane, Sushrut Karmalkar, Eric Price:
Robust Polynomial Regression up to the Information Theoretic Limit. 391-402
Session 5B
- Joran van Apeldoorn, András Gilyén, Sander Gribling, Ronald de Wolf:
Quantum SDP-Solvers: Better Upper and Lower Bounds. 403-414 - Fernando G. S. L. Brandão, Krysta M. Svore:
Quantum Speed-Ups for Solving Semidefinite Programs. 415-426 - Lior Eldar, Aram W. Harrow:
Local Hamiltonians Whose Ground States Are Hard to Approximate. 427-438 - András Pal Gilyén, Or Sattath:
On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma. 439-450 - Kun He, Liang Li, Xingwu Liu, Yuyi Wang, Mingji Xia:
Variable-Version Lovász Local Lemma: Beyond Shearer's Bound. 451-462 - Yinan Li, Youming Qiao:
Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model. 463-474
Session 6A
- Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh:
Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. 475-486 - Zeyuan Allen-Zhu, Yuanzhi Li:
First Efficient Convergence for Streaming k-PCA: A Global, Gap-Free, and Near-Optimal Rate. 487-492 - Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos:
Weighted k-Server Bounds via Combinatorial Dichotomies. 493-504 - Krati Nayyar, Sharath Raghvendra:
An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem. 505-515
Session 6B
- Yang Cai, Constantinos Daskalakis:
Learning Multi-Item Auctions with (or without) Samples. 516-527 - Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, Jennifer Wortman Vaughan:
Oracle-Efficient Online Learning and Auction Design. 528-539 - Paul Duetting, Michal Feldman, Thomas Kesselheim, Brendan Lucier:
Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs. 540-551 - Thomas Steinke, Jonathan R. Ullman:
Tight Lower Bounds for Differentially Private Selection. 552-563
Session 7A
- Dakshita Khurana, Amit Sahai:
How to Achieve Non-Malleability in One or Two Rounds. 564-575 - Huijia Lin, Rafael Pass, Pratik Soni:
Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles. 576-587 - Sanjam Garg, Akshayaram Srinivasan:
Garbled Protocols and Two-Round MPC from Bilinear Maps. 588-599 - Daniel Wichs, Giorgos Zirdelis:
Obfuscating Compute-and-Compare Programs under LWE. 600-611 - Rishab Goyal, Venkata Koppula, Brent Waters:
Lockable Obfuscation. 612-621 - Ilan Komargodski, Moni Naor, Eylon Yogev:
White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. 622-632
Session 7B
- Kasper Green Larsen, Jelani Nelson:
Optimality of the Johnson-Lindenstrauss Lemma. 633-638 - Noga Alon, Bo'az Klartag:
Optimal Compression of Approximate Inner Products and Dimension Reduction. 639-650 - Michael Kapralov:
Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average. 651-662 - Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Mikkel Thorup:
Fast Similarity Sketching. 663-671 - Cameron Musco, David P. Woodruff:
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. 672-683
Session 8
- Rasmus Kyng, Peng Zhang:
Hardness Results for Structured Linear Systems. 684-695 - Ola Svensson, Jakub Tarnawski:
The Matching Problem in General Graphs Is in Quasi-NC. 696-707
Session 9A
- Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan:
On the Power of Statistical Zero Knowledge. 708-719 - Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer:
The Power of Sum-of-Squares for Detecting Hidden Structures. 720-731 - Ran Raz:
A Time-Space Lower Bound for a Large Class of Learning Problems. 732-742 - Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan:
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. 743-754
Session 9B
- David R. Karger:
Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability. 755-766 - Glencora Borradaile, Hung Le, Christian Wulff-Nilsen:
Minor-Free Graphs Have Light Spanners. 767-778 - Ken-ichi Kawarabayashi, Anastasios Sidiropoulos:
Polylogarithmic Approximation for Minimum Planarization (Almost). 779-788 - Chandra Chekuri, Kent Quanrud:
Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time. 789-800
Session 10A
- Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan:
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. 801-812 - Rocco A. Servedio, Li-Yang Tan:
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. 813-823 - Rocco A. Servedio, Li-Yang Tan:
Fooling Intersections of Low-Weight Halfspaces. 824-835 - Benny Applebaum:
Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions. 836-847
Session 10B
- Noga Alon, Omri Ben-Eliezer, Eldar Fischer:
Testing Hereditary Properties of Ordered Graphs and Matrices. 848-858 - Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus:
A Characterization of Testable Hypergraph Properties. 859-867 - Xi Chen, Erik Waingarten, Jinyu Xie:
Boolean Unateness Testing with Õ(n3/4) Adaptive Queries. 868-879 - Tugkan Batu, Clément L. Canonne:
Generalized Uniformity Testing. 880-889
Session 11A
- Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson:
Much Faster Algorithms for Matrix Scaling. 890-901 - Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, Adrian Vladu:
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods. 902-913 - Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi:
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. 914-925 - David Durfee, John Peebles, Richard Peng, Anup B. Rao:
Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees. 926-937
Session 11B
- Thomas Dybdahl Ahle:
Optimal Las Vegas Locality Sensitive Data Structures. 938-949 - Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen:
Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. 950-961 - Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen:
Fast and Compact Exact Distance Oracle for Planar Graphs. 962-973
Session 12A
- Irit Dinur, Tali Kaufman:
High Dimensional Expanders Imply Agreement Expanders. 974-985 - Jingcheng Liu, Alistair Sinclair, Piyush Srivastava:
The Ising Partition Function: Zeros and Deterministic Approximation. 986-997 - Yin Tat Lee, Santosh Srinivas Vempala:
Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion. 998-1007
Session 12B
- Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. 1008-1019 - Javad B. Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi:
Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration. 1020-1031 - Moses Charikar, Paris Siminelakis:
Hashing-Based-Estimators for Kernel Density in High Dimensions. 1032-1043
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-07-10 20:44 CEST 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:
