default search action
22nd RANDOM / 21st APPROX 2018: Princeton, NJ, USA
- Eric Blais, Klaus Jansen, José D. P. Rolim, David Steurer:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA. LIPIcs 116, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-085-9 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xvi
- Akanksha Agrawal
, Daniel Lokshtanov, Pranabendu Misra
Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems. 1:1-1:15 - Sayan Bandyapadhyay, Neeraj Kumar, Subhash Suri, Kasturi R. Varadarajan:
Improved Approximation Bounds for the Minimum Constraint Removal Problem. 2:1-2:19 - Amariah Becker:
A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees. 3:1-3:15 - Aditya Bhaskara, Srivatsan Kumar:
Low Rank Approximation in the Presence of Outliers. 4:1-4:16 - Allan Borodin, Christodoulos Karavasilis, Denis Pankratov:
Greedy Bipartite Matching in Random Type Poisson Arrival Model. 5:1-5:15 - Mark Braverman, Young Kun-Ko:
Semi-Direct Sum Theorem and Nearest Neighbor under l_infty. 6:1-6:17 - Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou:
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. 7:1-7:22 - Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, Daniel Vaz
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs. 8:1-8:19 - Chandra Chekuri, Shalmoli Gupta:
Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations. 9:1-9:16 - Eden Chlamtác, Pasin Manurangsi:
Sherali-Adams Integrality Gaps Matching the Log-Density Threshold. 10:1-10:19 - Talya Eden, Will Rosenbaum:
Lower Bounds for Approximating Graph Parameters via Communication Complexity. 11:1-11:18 - Anat Ganor, Karthik C. S.
Communication Complexity of Correlated Equilibrium with Small Support. 12:1-12:16 - Ishay Haviv:
On Minrank and the Lovász Theta Function. 13:1-13:15 - Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu
Online Makespan Minimization: The Power of Restart. 14:1-14:19 - Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff:
On Sketching the q to p Norms. 15:1-15:20 - Janardhan Kulkarni, Shi Li:
Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models. 16:1-16:21 - Amit Levi
Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices. 17:1-17:19 - Yi Li
Deterministic Heavy Hitters with Sublinear Query Time. 18:1-18:18 - Yi Li
On Low-Risk Heavy Hitters and Sparse Recovery Schemes. 19:1-19:13 - Pasin Manurangsi, Luca Trevisan
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut. 20:1-20:17 - Shyam Narayanan:
Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers. 21:1-21:19 - Goonwanth Reddy, Rahul Vaze:
Robust Online Speed Scaling With Deadline Uncertainty. 22:1-22:17 - Richard Santiago, F. Bruce Shepherd:
Multi-Agent Submodular Optimization. 23:1-23:20 - Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai:
Generalized Assignment of Time-Sensitive Item Groups. 24:1-24:18 - Suvrit Sra, Nisheeth K. Vishnoi, Ozan Yildiz:
On Geodesically Convex Formulations for the Brascamp-Lieb Constant. 25:1-25:15 - Joseph Swernofsky:
Tensor Rank is Hard to Approximate. 26:1-26:9 - Hao-Ting Wei, Wing-Kai Hon, Paul Horn, Chung-Shou Liao, Kunihiko Sadakane
An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity. 27:1-27:14 - Andreas Wiese
Fixed-Parameter Approximation Schemes for Weighted Flowtime. 28:1-28:19 - László Babai
List-Decoding Homomorphism Codes with Arbitrary Codomains. 29:1-29:18 - Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo:
Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources. 30:1-30:15 - Aleksandrs Belovs:
Adaptive Lower Bound for Testing Monotonicity on the Line. 31:1-31:10 - Antonio Blanca, Zongchen Chen, Eric Vigoda:
Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region. 32:1-32:18 - Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. 33:1-33:15 - Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan:
Polar Codes with Exponentially Small Error at Finite Block Length. 34:1-34:17 - Mark Bun, Justin Thaler:
Approximate Degree and the Complexity of Depth Three Circuits. 35:1-35:18 - Corrie Jacobien Carstens, Pieter Kleer:
Speeding up Switch Markov Chains for Sampling Bipartite Graphs with Given Degree Sequence. 36:1-36:18 - Kuan Cheng, Xin Li:
Randomness Extraction in AC0 and with Small Locality. 37:1-37:20 - Yotam Dikstein, Irit Dinur
Boolean Function Analysis on High-Dimensional Expanders. 38:1-38:20 - Peter Gracar
Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents. 39:1-39:17 - Elena Grigorescu, Akash Kumar, Karl Wimmer:
Flipping out with Many Flips: Hardness of Testing k-Monotonicity. 40:1-40:17 - Venkatesan Guruswami, Chaoping Xing, Chen Yuan
How Long Can Optimal Locally Repairable Codes Be?. 41:1-41:11 - Ishay Haviv:
On Minrank and Forbidden Subgraphs. 42:1-42:14 - William M. Hoza, Adam R. Klivans:
Preserving Randomness for Adaptive Algorithms. 43:1-43:19 - Fotis Iliopoulos:
Commutative Algorithms Approximate the LLL-distribution. 44:1-44:20 - Tony Johansson:
The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree. 45:1-45:14 - Valentine Kabanets, Zhenjian Lu:
Satisfiability and Derandomization for Small Polynomial Threshold Circuits. 46:1-46:19 - Tali Kaufman, Izhar Oppenheim
High Order Random Walks: Beyond Spectral Gap. 47:1-47:17 - Sajin Koroth, Or Meir:
Improved Composition Theorems for Functions and Relations. 48:1-48:18 - Maya Leshkowitz:
Round Complexity Versus Randomness Complexity in Interactive Proofs. 49:1-49:16 - Ray Li, Mary Wootters:
Improved List-Decodability of Random Linear Binary Codes. 50:1-50:19 - Xin Li, Shachar Lovett
Sunflowers and Quasi-Sunflowers from Randomness Extractors. 51:1-51:13 - Tianyu Liu:
Torpid Mixing of Markov Chains for the Six-vertex Model on Z^2. 52:1-52:15 - Yonatan Nakar, Dana Ron
On the Testability of Graph Partition Properties. 53:1-53:13 - Ryan O'Donnell, Yu Zhao:
On Closeness to k-Wise Uniformity. 54:1-54:19 - Igor Carboni Oliveira, Rahul Santhanam
Pseudo-Derandomizing Learning and Approximation. 55:1-55:19 - Rocco A. Servedio
Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. 56:1-56:20 - Shai Vardi:
Randomly Coloring Graphs of Logarithmically Bounded Pathwidth. 57:1-57:19 - Michael Viderman:
Explicit Strong LTCs with Inverse Poly-Log Rate and Constant Soundness. 58:1-58:14
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-06 23:27 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: