default search action
59th FOCS 2018: Paris, France
- Mikkel Thorup:
59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018. IEEE Computer Society 2018, ISBN 978-1-5386-4230-6 - Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, Nicole Tomczak-Jaegermann:
Balancing Vectors in Any Norm. 1-10 - Hossein Esfandiari, Michael Mitzenmacher:
Metric Sublinear Algorithms via Linear Sampling. 11-22 - Lior Eldar, Saeed Mehraban
:
Approximating the Permanent of a Random Matrix with Vanishing Mean. 23-34 - Nima Anari
Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids. 35-46 - Arkadev Chattopadhyay, Nikhil S. Mande
A Short List of Equalities Induces Large Sign Rank. 47-58 - William Hoza, David Zuckerman:
Simple Optimal Hitting Sets for Small-Success RL. 59-64 - Igor Carboni Oliveira, Rahul Santhanam:
Hardness Magnification for Natural Problems. 65-76 - Oded Goldreich, Guy N. Rothblum:
Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems. 77-88 - Martin Grohe, Daniel Neuen
A Faster Isomorphism Test for Graphs of Small Degree. 89-100 - Matthew Fahrbach, Gary L. Miller, Richard Peng, Saurabh Sawlani, Junxing Wang, Shen Chen Xu:
Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm. 101-112 - Anupam Gupta
Faster Exact and Approximate Algorithms for k-Cut. 113-123 - Justin Holmgren
Delegating Computations with (Almost) Minimal Time and Space Overhead. 124-135 - Iftach Haitner, Kobbi Nissim, Eran Omri
Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols. 136-147 - Katerina Sotiraki
PPP-Completeness with Connections to Cryptography. 148-158 - Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
Hölder Homeomorphisms and Approximate Nearest Neighbors. 159-169 - Shiri Chechik:
Near-Optimal Approximate Decremental All Pairs Shortest Paths. 170-181 - Michael A. Bender, Martin Farach-Colton
Bloom Filters, Adaptivity, and the Dictionary Problem. 182-193 - Shachar Lovett:
MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture. 194-199 - Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu:
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors. 200-211 - Swastik Kopparty, Noga Ron-Zewi
Improved Decoding of Folded Reed-Solomon and Multiplicity Codes. 212-223 - Natan Rubin
An Improved Bound for Weak Epsilon-Nets in the Plane. 224-235 - Clément Carbonnel
The Complexity of General-Valued CSPs Seen from the Other Side. 236-246 - Shuichi Hirahara:
Non-Black-Box Worst-Case to Average-Case Reductions within NP. 247-258 - Urmila Mahadev:
Classical Verification of Quantum Computations. 259-267 - Renato Paes Leme, Jon Schneider:
Contextual Search via Intrinsic Volumes. 268-282 - Pranjal Awasthi, Aravindan Vijayaraghavan:
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports. 283-296 - Anindya De, Philip M. Long, Rocco A. Servedio
Learning Sums of Independent Random Variables with Sparse Collective Support. 297-308 - Robert Kleinberg, Nicole Immorlica:
Recharging Bandits. 309-319 - Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick:
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. 320-331 - Urmila Mahadev:
Classical Homomorphic Encryption for Quantum Circuits. 332-338 - Shalev Ben-David, Adam Bouland
Classical Lower Bounds from Quantum Upper Bounds. 339-349 - Jeongwan Haah, Matthew B. Hastings, Robin Kothari
Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians. 350-360 - Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions. 361-372 - Rasmus Kyng, Zhao Song:
A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees. 373-384 - Huan Li, Aaron Schild:
Spectral Subspace Sparsification. 385-396 - Mika Göös, Aviad Rubinstein:
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. 397-403 - Yiding Feng
An End-to-End Argument in Mechanism Design (Prior-Independent Auctions for Budgeted Agents). 404-415 - Yannai A. Gonczarowski, S. Matthew Weinberg
The Sample Complexity of Up-to-ε Multi-Dimensional Revenue Maximization. 416-426 - Yossi Azar, Noam Touitou
Improved Online Algorithm for Weighted Flow Time. 427-437 - James R. Lee:
Fusible HSTs and the Randomized k-Server Conjecture. 438-449 - Mark de Berg
An ETH-Tight Exact Algorithm for Euclidean TSP. 450-461 - Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida:
0/1/All CSPs, Half-Integral A-Path Packing, and Linear-Time FPT Algorithms. 462-473 - Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs. 474-484 - Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. 485-496 - Ashish Chiplunkar, Michael Kapralov
Testing Graph Clusterability: Algorithms and Lower Bounds. 497-508 - Akash Kumar, C. Seshadhri, Andrew Stolman:
Finding Forbidden Minors in Sublinear Time: A n^1/2+o(1)-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs. 509-520 - Vitaly Feldman, Ilya Mironov, Kunal Talwar, Abhradeep Thakurta:
Privacy Amplification by Iteration. 521-532 - Christian Borgs
Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation. 533-543 - Rajesh Jayaram, David P. Woodruff:
Perfect Lp Sampling in a Data Stream. 544-555 - John Kallaugher, Michael Kapralov
The Sketching Complexity of Graph and Hypergraph Counting. 556-567 - Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet
EPTAS for Max Clique on Disks and Unit Balls. 568-579 - Josh Alman, Virginia Vassilevska Williams:
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. 580-591 - Subhash Khot, Dor Minzer, Muli Safra
Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion. 592-601 - Johan Håstad:
Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs. 602 - Maria-Florina Balcan, Travis Dick, Ellen Vitercik:
Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization. 603-614 - Arturs Backurs, Moses Charikar
Efficient Density Evaluation for Smooth Kernels. 615-626 - Allen Liu, Ankur Moitra:
Efficiently Learning Mixtures of Mallows Models. 627-638 - Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos
Efficient Statistics, in High Dimensions, from Truncated Samples. 639-649 - Nima Anari
Planar Graph Perfect Matching Is in NC. 650-661 - Mohsen Ghaffari, David G. Harris, Fabian Kuhn:
On Derandomizing Local Distributed Algorithms. 662-673 - Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong:
Parallel Graph Connectivity in Log Diameter Rounds. 674-685 - Sebastian Forster
A Faster Distributed Single-Source Shortest Paths Algorithm. 686-697 - Asaf Ferber, Vishesh Jain:
1-Factorizations of Pseudorandom Graphs. 698-708 - Marco Bressan, Enoch Peserico, Luca Pretto:
Sublinear Algorithms for Local Graph Centrality Estimation. 709-718 - Bojan Mohar, Yifan Jing
Efficient Polynomial-Time Approximation Scheme for the Genus of Dense Graphs. 719-730 - Anand Natarajan, Thomas Vidick:
Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. 731-742 - Omar Fawzi
Constant Overhead Quantum Fault-Tolerance with Quantum Expander Codes. 743-754 - Alessandro Chiesa, Michael A. Forbes, Tom Gur
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. 755-765 - Vera Traub
Beating the Integrality Ratio for s-t-Tours in Graphs. 766-777 - Jatin Batra, Naveen Garg
Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time. 778-789 - Marek Adamczyk, Michal Wlodarczyk:
Random Order Contention Resolution Schemes. 790-801 - Christian Sohler
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. 802-813 - Lingxiao Huang
Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. 814-825 - Marshall Ball
Non-Malleable Codes for Small-Depth Circuits. 826-837 - Amos Beimel
Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling. 838-849 - Justin Holmgren
Cryptographic Hashing from Strong One-Way Functions (Or: One-Way Product Functions and Their Applications). 850-858 - Willy Quach, Hoeteck Wee, Daniel Wichs:
Laconic Function Evaluation and Applications. 859-870 - Sarvar Patel, Giuseppe Persiano, Mariana Raykova, Kevin Yeo:
PanORAMa: Oblivious RAM with Logarithmic Overhead. 871-882 - Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter
Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes. 883-897 - Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford:
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. 898-909 - Laura Sanità:
The Diameter of the Fractional Matching Polytope and Its Hardness Implications. 910-921 - Aaron Sidford, Kevin Tian:
Coordinate Methods for Accelerating ℓ∞ Regression and Faster Approximate Maximum Flow. 922-933 - Suryajith Chillara, Christian Engels
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. 934-945 - Michael A. Forbes, Zander Kelley:
Pseudorandom Generators for Read-Once Branching Programs, in Any Order. 946-955 - Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola:
Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs. 956-966 - Mert Saglam:
Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences. 967-978 - Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. 979-990
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-01-26 23:57 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: