default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID59th 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, Shayan Oveis Gharan, Cynthia Vinzant:
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, Pascal Schweitzer:
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, Euiwoong Lee, Jason Li:
Faster Exact and Approximate Algorithms for k-Cut. 113-123 - Justin Holmgren, Ron Rothblum:
Delegating Computations with (Almost) Minimal Time and Space Overhead. 124-135 - Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak:
Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols. 136-147 - Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis:
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, Mayank Goswami, Rob Johnson, Samuel McCauley, Shikha Singh:
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, Shubhangi Saraf, Mary Wootters:
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, Miguel Romero, Stanislav Zivný:
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, Ankit Garg, Robin Kothari:
Classical Lower Bounds from Quantum Upper Bounds. 339-349 - Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low:
Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians. 350-360 - Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang:
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, Jason D. Hartline:
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, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Sudeshna Kolay:
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, Sanjeev Khanna, Aida Mousavifar, Yuval Peres:
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, Jennifer T. Chayes, Adam D. Smith, Ilias Zadik:
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, Eric Price:
The Sketching Complexity of Graph and Hypergraph Counting. 556-567 - Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé:
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, Piotr Indyk, Paris Siminelakis:
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, Manolis Zampetakis:
Efficient Statistics, in High Dimensions, from Truncated Samples. 639-649 - Nima Anari, Vijay V. Vazirani:
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, Danupon Nanongkai:
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, Antoine Grospellier, Anthony Leverrier:
Constant Overhead Quantum Fault-Tolerance with Quantum Expander Codes. 743-754 - Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner:
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. 755-765 - Vera Traub, Jens Vygen:
Beating the Integrality Ratio for s-t-Tours in Graphs. 766-777 - Jatin Batra, Naveen Garg, Amit Kumar:
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, David P. Woodruff:
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. 802-813 - Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, Xuan Wu:
Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. 814-825 - Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan:
Non-Malleable Codes for Small-Depth Circuits. 826-837 - Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri:
Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling. 838-849 - Justin Holmgren, Alex Lombardi:
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, Avi Wigderson:
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, Nutan Limaye, Srikanth Srinivasan:
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ý, Michael E. Saks:
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-12-04 01:33 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:
