default search action
50th STOC 2018: Los Angeles, CA, USA
- Ilias Diakonikolas, David Kempe, Monika Henzinger:
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018. ACM 2018
Invited Talks (Partial List)
- Irene Lo:
Dynamic matching in school choice: efficient seat reassignment after late cancellations (invited talk). 1 - Tengyu Ma:
Generalization and equilibrium in generative adversarial nets (GANs) (invited talk). 2
Session 1A
- Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, Aleksander Madry:
k-server via multiscale entropic regularization. 3-16 - Zhiyi Huang
, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu
How to match when all vertices arrive online. 17-29 - Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, Maryam Shadloo:
Online load balancing on related machines. 30-43
Session 1B
- Constantinos Daskalakis, Christos Tzamos
A converse to Banach's fixed point theorem and its CLS-completeness. 44-50 - Aris Filos-Ratsikas
Consensus halving is PPA-complete. 51-64 - Mikkel Abrahamsen
The art gallery problem is ∃ ℝ-complete. 65-73
Session 1C
- Mark Bun, Cynthia Dwork, Guy N. Rothblum, Thomas Steinke:
Composable and versatile privacy via truncated CDP. 74-86 - Bartlomiej Dudek
Universal protocols for information dissemination using emergent signals. 87-99 - Hamed Omidvar
Shape of diffusion and size of monochromatic region of a two-dimensional spin system. 100-113
Session 2A
- Thodoris Lykouris
Stochastic bandits robust to adversarial corruptions. 114-122 - Yannai A. Gonczarowski:
Bounding the menu-size of approximately optimal auctions via optimal-transport duality. 123-131 - Darrell Hoy, Samuel Taggart, Zihe Wang:
A tighter welfare guarantee for first-price auctions. 132-137
Session 2B
- Daniel Neuen
An exponential lower bound for individualization-refinement algorithms for graph isomorphism. 138-150 - Cornelius Brand
Extensor-coding. 151-164 - Krzysztof Onak, Xiaorui Sun:
The query complexity of graph isomorphism: bypassing distribution testing lower bounds. 165-171
Session 2C
- Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson:
Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. 172-181 - Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Akshay Ramachandran:
The Paulsen problem, continuous operator scaling, and smoothed analysis. 182-189 - Cole Franks:
Operator scaling with specified marginals. 190-203
STOC Award Papers
- Ola Svensson, Jakub Tarnawski, László A. Végh
A constant-factor approximation algorithm for the asymmetric traveling salesman problem. 204-213 - Aaron Schild:
An almost-linear time algorithm for uniform random spanning tree generation. 214-227
Session 3A
- Divesh Aggarwal, Noah Stephens-Davidowitz:
(Gap/S)ETH hardness of SVP. 228-238 - Udit Agarwal, Vijaya Ramachandran:
Fine-grained complexity for sparse graphs. 239-252 - Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof
More consequences of falsifying SETH and the orthogonal vectors conjecture. 253-266 - Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein:
Towards tight approximation bounds for graph diameter and eccentricities. 267-280 - Holger Dell, John Lapinskas
Fine-grained reductions from approximate counting to decision. 281-288
Session 3B
- Matthias Christandl, Péter Vrana
Universal points in the asymptotic spectrum of tensors. 289-296 - Mark Bun, Robin Kothari
The polynomial method strikes back: tight quantum query bounds via dual polynomials. 297-310 - Alexander A. Sherstov:
Algorithmic polynomials. 311-324 - Scott Aaronson:
Shadow tomography of quantum states. 325-338 - Debbie W. Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu
Capacity approaching coding for low noise interactive quantum communication. 339-352
Session 3C
- Mark Braverman, Gil Cohen, Sumegha Garg:
Hitting sets with near-optimal error for read-once branching programs. 353-362 - Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal:
Improved pseudorandomness for unordered branching programs through local monotonicity. 363-375 - Irit Dinur
Towards a proof of the 2-to-1 games conjecture? 376-389 - Daniel Dadush, Sophie Huiberts:
A friendly smoothed analysis of the simplex method. 390-403 - Rasmus Kyng, Richard Peng, Robert Schwieterman, Peng Zhang:
Incomplete nested dissection. 404-417
Session 4A
- Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara Uitto:
Deterministic distributed edge-coloring with fewer colors. 418-430 - Mohsen Ghaffari, Jason Li:
Improved distributed algorithms for exact shortest paths. 431-444 - Yi-Jun Chang
An optimal distributed (Δ+1)-coloring algorithm? 445-456 - Jeremy T. Fineman:
Nearly work-efficient parallel algorithm for digraph reachability. 457-470 - Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski:
Round compression for parallel matching algorithms. 471-484
Session 4B
- Jaroslaw Blasiok
General strong polarization. 485-492 - Mahdi Cheraghchi
Capacity upper bounds for deletion-type channels. 493-506 - Klim Efremenko
Interactive coding over the noisy broadcast channel. 507-520 - Omar Fawzi
Efficient decoding of random errors for quantum expander codes. 521-534 - Gil Cohen, Bernhard Haeupler, Leonard J. Schulman
Explicit binary tree codes with polylogarithmic size alphabet. 535-544
Session 4C
- Jesús A. De Loera, Jamie Haddock, Luis Rademacher
The minimum euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential. 545-553 - Daniel M. Kane, Shachar Lovett
Near-optimal linear decision trees for k-SUM and related problems. 554-563 - Mikkel Abrahamsen
Fast fencing. 564-573 - Mark de Berg
A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs. 574-586 - Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
The gram-schmidt walk: a cure for the Banaszczyk blues. 587-597
Session 5A
- Yuval Emek, Shay Kutten, Ron Lavi
Approximating generalized network design under (dis)economies of scale with applications to energy efficiency. 598-606 - Fabrizio Grandoni
A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes. 607-619 - Jaroslaw Byrka
Constant-factor approximation for ordered k-median. 620-631 - Fabrizio Grandoni
Improved approximation for tree augmentation: saving by rewiring. 632-645 - Ravishankar Krishnaswamy, Shi Li, Sai Sandeep:
Constant approximation for k-median and k-means with outliers via iterative rounding. 646-659
Session 5B
- Rishab Goyal, Venkata Koppula, Brent Waters:
Collusion resistant traitor tracing from learning with errors. 660-670 - Nir Bitansky, Yael Tauman Kalai, Omer Paneth:
Multi-collision resistance: a paradigm for keyless hash functions. 671-684 - Vipul Goyal, Ashutosh Kumar:
Non-malleable secret sharing. 685-698 - Tianren Liu
Breaking the circuit-size barrier in secret sharing. 699-708 - Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs:
Succinct delegation for low-space non-deterministic computation. 709-721
Session 5C
- Talya Eden, Dana Ron
On approximating the number of k-cliques in sublinear time. 722-734 - Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Testing conditional independence of discrete distributions. 735-748 - Zhengyang Liu, Xi Chen, Rocco A. Servedio
Distribution-free junta testing. 749-759 - Lior Gishboliner, Asaf Shapira:
A generalized Turán problem and its applications. 760-772 - Tali Kaufman, Izhar Oppenheim
Construction of new local spectral high dimensional expanders. 773-786
Session 6A
- Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
Data-dependent hashing via nonlinear spectral gaps. 787-800 - László Kozma, Thatchaphol Saranurak
Smooth heaps and a dual view of self-adjusting data structures. 801-814 - Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon:
Fully dynamic maximal independent set with sublinear update time. 815-826 - Dominik Kempa
At the roots of dictionary compression: string attractors. 827-840 - Bernhard Haeupler, Amirbehshad Shahrasbi
Synchronization strings: explicit constructions, local decoding, and applications. 841-854
Session 6B
- Roei Tell:
Quantified derandomization of linear threshold circuits. 855-865 - Albert Atserias, Ilario Bonacina
Clique is hard on average for regular resolution. 866-877 - Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov
On the complexity of hazard-free circuits. 878-889 - Cody Murray, R. Ryan Williams:
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. 890-901 - Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
Monotone circuit lower bounds from resolution. 902-911
Session 6C
- Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
Sparse Kneser graphs are Hamiltonian. 912-919 - Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber
A simply exponential upper bound on the maximum number of stable matchings. 920-925 - Heng Guo, Chao Liao, Pinyan Lu
Counting hypergraph colourings in the local lemma regime. 926-939 - Irit Dinur
On non-optimally expanding sets in Grassmann graphs. 940-951 - Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman:
Metric embedding via shortest path decompositions. 952-963
Session 7A
- Mark Braverman, Gillat Kol:
Interactive compression to external information. 964-977 - Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. 978-989 - Sumegha Garg, Ran Raz
Extractor-based time-space lower bounds for learning. 990-1002 - Josh Alman, Joshua R. Wang, Huacheng Yu:
Cell-probe lower bounds from online communication complexity. 1003-1012 - Arkadev Chattopadhyay, Michal Koucký
Simulation beats richness: new data-structure lower bounds. 1013-1020
Session 7B
- Samuel B. Hopkins, Jerry Li:
Mixture models, robustness, and sum of squares proofs. 1021-1034 - Pravesh K. Kothari, Jacob Steinhardt, David Steurer
Robust moment estimation and improved clustering via sum of squares. 1035-1046 - Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
List-decodable robust mean estimation and learning mixtures of spherical gaussians. 1047-1060 - Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Learning geometric concepts with nasty noise. 1061-1073 - Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant:
Prediction with a short memory. 1074-1087 - Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn:
Nonlinear dimension reduction via outer Bi-Lipschitz extensions. 1088-1101
Session 7C
- Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava:
A matrix expander Chernoff bound. 1102-1114 - Yin Tat Lee, Santosh S. Vempala:
Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation. 1115-1121 - Yin Tat Lee, Santosh S. Vempala:
Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev. 1122-1129 - Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li:
An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time. 1130-1137 - Eric Balkanski, Yaron Singer:
The adaptive complexity of maximizing a submodular function. 1138-1151
Session 8A
- Pranjal Dutta, Nitin Saxena
Discovering the roots: uniform closure results for algebraic classes under factoring. 1152-1165 - Manindra Agrawal, Sumanta Ghosh, Nitin Saxena
Bootstrapping variables in algebraic circuits. 1166-1179 - Michael A. Forbes, Amir Shpilka
A PSPACE construction of a hitting set for the closure of small algebraic circuits. 1180-1192 - Markus Bläser, Christian Ikenmeyer, Gorav Jindal
Generalized matrix completion and algebraic natural proofs. 1193-1206 - Toniann Pitassi, Robert Robere:
Lifting nullstellensatz to monotone span programs over any field. 1207-1219
Session 8B
- Julia Chuzhoy, David H. K. Kim, Rachit Nimavat:
Almost polynomial hardness of node-disjoint paths in grids. 1220-1233 - Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Inapproximability of the independent set polynomial in the complex plane. 1234-1240 - Pravesh K. Kothari, Ruta Mehta:
Sum-of-squares meets nash: lower bounds for finding any equilibrium. 1241-1248 - Max Simchowitz, Ahmed El Alaoui, Benjamin Recht:
Tight query complexity lower bounds for PCA via finite sample deformed wigner law. 1249-1259 - Aviad Rubinstein:
Hardness of approximate nearest neighbor search. 1260-1268
Session 8C
- MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, Cliff Stein:
Fast algorithms for knapsack via convolution and prediction. 1269-1282 - Karthik C. S.
On the parameterized complexity of approximating dominating set. 1283-1296 - Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen:
Tight cell probe bounds for succinct Boolean matrix-vector multiplication. 1297-1306 - Alkida Balliu
New classes of distributed time complexity. 1307-1318 - Jeff Erickson, Kyle Fox, Luvsandondov Lkhamsuren:
Holiest minimum-cost paths and flows in surface graphs. 1319-1332
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 2024-11-22 19:46 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: