default search action
23rd RANDOM / 22nd APPROX 2019: Cambridge, MA, USA
- Dimitris Achlioptas, László A. Végh:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA. LIPIcs 145, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2019, ISBN 978-3-95977-125-2 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:22
- Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
:
The Query Complexity of Mastermind with lp Distances. 1:1-1:11 - Chi-Ning Chou, Zhixian Lei, Preetum Nakkiran:
Tracking the l2 Norm with Constant Update Time. 2:1-2:15 - Benjamin Moseley
Submodular Optimization with Contention Resolution Extensions. 3:1-3:17 - David Ellis Hershkowitz, R. Ravi, Sahil Singla:
Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty. 4:1-4:19 - Venkatesan Guruswami
Streaming Hardness of Unique Games. 5:1-5:12 - Arnold Filtser:
On Strong Diameter Padded Decompositions. 6:1-6:21 - Alon Eden, Uriel Feige, Michal Feldman:
Max-Min Greedy Matching. 7:1-7:23 - Gary L. Miller, Noel J. Walkington, Alex L. Wang:
Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues. 8:1-8:19 - Prahladh Harsha
Improved 3LIN Hardness via Linear Label Cover. 9:1-9:16 - Ilan Reuven Cohen, Alon Eden, Amos Fiat, Lukasz Jez:
Dynamic Pricing of Servers on Trees. 10:1-10:22 - Eden Chlamtác, Michael Dinitz
Approximating the Norms of Graph Spanners. 11:1-11:22 - Dhruv Rohatgi:
Conditional Hardness of Earth Mover Distance. 12:1-12:17 - Reyna Hulett
Single-Elimination Brackets Fail to Approximate Copeland Winner. 13:1-13:20 - Timothy Carpenter, Ario Salmasi, Anastasios Sidiropoulos:
Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion. 14:1-14:15 - Venkatesan Guruswami, Sai Sandeep:
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms. 15:1-15:17 - Eric Allender
Syntactic Separation of Subset Satisfiability Problems. 16:1-16:23 - Dimitris Fotakis
Malleable Scheduling Beyond Identical Machines. 17:1-17:14 - Ioana Oriana Bercea
On the Cost of Essentially Fair Clusterings. 18:1-18:22 - Neeraj Kumar, Stavros Sintos, Subhash Suri:
The Maximum Exposure Problem. 19:1-19:20 - Sagar Kale
Small Space Stream Summary for Matroid Center. 20:1-20:22 - Alexander Birx, Yann Disser, Kevin Schewior
Improved Bounds for Open Online Dial-a-Ride on the Line. 21:1-21:22 - Susanne Albers, Arindam Khan, Leon Ladewig:
Improved Online Algorithms for Knapsack and GAP in the Random Order Model. 22:1-22:23 - Kent Quanrud:
Fast and Deterministic Approximations for k-Cut. 23:1-23:20 - Per Austrin
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder. 24:1-24:17 - Andreas S. Schulz, Rajan Udwani:
Robust Appointment Scheduling with Heterogeneous Costs. 25:1-25:17 - Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, Maksim Nikolaev
Collapsing Superstring Conjecture. 26:1-26:23 - Vladimir Braverman, Harry Lang, Enayat Ullah, Samson Zhou:
Improved Algorithms for Time Decay Streams. 27:1-27:17 - Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury:
Approximation Algorithms for Partially Colorable Graphs. 28:1-28:20 - Rajesh Jayaram, David P. Woodruff:
Towards Optimal Moment Estimation in Streaming and Distributed Models. 29:1-29:21 - Umang Bhaskar, Gunjan Kumar:
The Complexity of Partial Function Extension for Coverage Functions. 30:1-30:21 - Sevag Gharibian, Ojas Parekh:
Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. 31:1-31:17 - Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, Nabil H. Mustafa:
Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint. 32:1-32:21 - Devvrit, Ravishankar Krishnaswamy, Nived Rajaraman:
Robust Correlation Clustering. 33:1-33:18 - Chao Liao, Jiabao Lin, Pinyan Lu
Counting Independent Sets and Colorings on Random Regular Bipartite Graphs. 34:1-34:12 - Josep Díaz, Mordecai J. Golin
The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions. 35:1-35:14 - Michael Anastos, Alan M. Frieze:
On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs. 36:1-36:10 - Matthew Fahrbach, Dana Randall:
Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases. 37:1-37:20 - Ray Li, Mary Wootters:
Lifted Multiplicity Codes and the Disjoint Repair Group Property. 38:1-38:18 - Grant Schoenebeck
Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization. 39:1-39:20 - Irit Dinur
Direct Sum Testing: The General Case. 40:1-40:11 - Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins
Fast Algorithms at Low Temperatures via Markov Chains. 41:1-41:14 - Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan:
Deterministic Approximation of Random Walks in Small Space. 42:1-42:22 - Avraham Ben-Aroya, Gil Cohen, Dean Doron
Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. 43:1-43:20 - Frank Ban, Xi Chen, Rocco A. Servedio
Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. 44:1-44:18 - Rocco A. Servedio
Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. 45:1-45:23 - Bruce Spang, Mary Wootters:
Unconstraining Graph-Constrained Group Testing. 46:1-46:20 - Ioannis Z. Emiris
Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of l1. 47:1-47:13 - Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda:
Improved Strong Spatial Mixing for Colorings on Trees. 48:1-48:16 - Domagoj Bradac
(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing. 49:1-49:21 - Roy Gotlib, Tali Kaufman:
Testing Odd Direct Sums Using High Dimensional Expanders. 50:1-50:20 - Mika Göös, Thomas Watson:
A Lower Bound for Sampling Disjoint Sets. 51:1-51:13 - Ronitt Rubinfeld, Arsen Vasilyan:
Approximating the Noise Sensitivity of a Monotone Boolean Function. 52:1-52:17 - Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha:
Connectivity of Random Annulus Graphs and the Geometric Block Model. 53:1-53:23 - Sarah Cannon
A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. 54:1-54:22 - Mark Bun, Justin Thaler:
The Large-Error Approximate Degree of AC0. 55:1-55:16 - Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar:
String Matching: Communication, Circuits, and Learning. 56:1-56:20 - Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay:
Efficient Black-Box Identity Testing for Free Group Algebras. 57:1-57:16 - Charlotte Knierim
The Maximum Label Propagation Algorithm on Sparse Random Graphs. 58:1-58:15 - Rohit Agrawal
Samplers and Extractors for Unbounded Functions. 59:1-59:21 - Svante Janson
Successive Minimum Spanning Trees. 60:1-60:16 - Meena Jagadeesan:
Simple Analysis of Sparse, Sign-Consistent JL. 61:1-61:20 - Vladimir Braverman, Dan Feldman, Harry Lang, Daniela Rus:
Streaming Coreset Constructions for M-Estimators. 62:1-62:15 - Shyam Narayanan:
Pairwise Independent Random Walks Can Be Slightly Unbounded. 63:1-63:19 - Zongchen Chen, Santosh S. Vempala:
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions. 64:1-64:12 - Amos Beimel
Exploring Differential Obliviousness. 65:1-65:20 - Michael Anastos
Thresholds in Random Motif Graphs. 66:1-66:19 - Antonio Blanca, Reza Gheissari, Eric Vigoda:
Random-Cluster Dynamics in Z2: Rapid Mixing with General Boundary Conditions. 67:1-67:19 - Swastik Kopparty, Nicolas Resch
On List Recovery of High-Rate Tensor Codes. 68:1-68:22 - Grigory Yaroslavtsev, Samson Zhou:
Approximate F2-Sketching of Valuation Functions. 69:1-69:21 - Amit Chakrabarti
Streaming Verification of Graph Computations via Graph Structure. 70:1-70:20 - Andrej Bogdanov, Nikhil S. Mande
Approximate Degree, Secret Sharing, and Concentration Phenomena. 71:1-71:21 - Fu Li, David Zuckerman:
Improved Extractors for Recognizable and Algebraic Sources. 72:1-72:22
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-13 00:50 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: