Portal - APPROX/RANDOM 2018

APPROX/RANDOM 2018	August 20-22, 2018 - Princeton, NJ, USA
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) Eric Blais and Klaus Jansen and José D. P. Rolim and David Steurer (Eds.)
ISBN 978-3-95977-085-9, LIPICS Vol. 116	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 31 MB)
Search Publication Server

Authors

Carboni Oliveira, Igor

Carstens, Corrie Jacobien

Guruswami, Venkatesan

Karavasilis, Christodoulos

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Blais, Eric ; Jansen, Klaus ; D. P. Rolim, José ; Steurer, David

Abstract | Document (358 KB) | BibTeX

Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems

Authors: Agrawal, Akanksha ; Lokshtanov, Daniel ; Misra, Pranabendu ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (522 KB) | BibTeX

Improved Approximation Bounds for the Minimum Constraint Removal Problem

Authors: Bandyapadhyay, Sayan ; Kumar, Neeraj ; Suri, Subhash ; Varadarajan, Kasturi

Abstract | Document (830 KB) | BibTeX

A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees

Authors: Becker, Amariah

Abstract | Document (676 KB) | BibTeX

Low Rank Approximation in the Presence of Outliers

Authors: Bhaskara, Aditya ; Kumar, Srivatsan

Abstract | Document (513 KB) | BibTeX

Greedy Bipartite Matching in Random Type Poisson Arrival Model

Authors: Borodin, Allan ; Karavasilis, Christodoulos ; Pankratov, Denis

Abstract | Document (673 KB) | BibTeX

Semi-Direct Sum Theorem and Nearest Neighbor under l_infty

Authors: Braverman, Mark ; Ko, Young Kun

Abstract | Document (509 KB) | BibTeX

Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows

Authors: Braverman, Vladimir ; Grigorescu, Elena ; Lang, Harry ; Woodruff, David P. ; Zhou, Samson

Abstract | Document (645 KB) | BibTeX

Survivable Network Design for Group Connectivity in Low-Treewidth Graphs

Authors: Chalermsook, Parinya ; Das, Syamantak ; Even, Guy ; Laekhanukit, Bundit ; Vaz, Daniel

Abstract | Document (552 KB) | BibTeX

Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations

Authors: Chekuri, Chandra ; Gupta, Shalmoli

Abstract | Document (823 KB) | BibTeX

Sherali-Adams Integrality Gaps Matching the Log-Density Threshold

Authors: Chlamtác, Eden ; Manurangsi, Pasin

Abstract | Document (570 KB) | BibTeX

Lower Bounds for Approximating Graph Parameters via Communication Complexity

Authors: Eden, Talya ; Rosenbaum, Will

Abstract | Document (560 KB) | BibTeX

Communication Complexity of Correlated Equilibrium with Small Support

Authors: Ganor, Anat ; C. S., Karthik

Abstract | Document (529 KB) | BibTeX

On Minrank and the Lovász Theta Function

Authors: Haviv, Ishay

Abstract | Document (366 KB) | BibTeX

Online Makespan Minimization: The Power of Restart

Authors: Huang, Zhiyi ; Kang, Ning ; Tang, Zhihao Gavin ; Wu, Xiaowei ; Zhang, Yuhao

Abstract | Document (571 KB) | BibTeX

On Sketching the q to p Norms

Authors: Krishnan, Aditya ; Mohanty, Sidhanth ; Woodruff, David P.

Abstract | Document (621 KB) | BibTeX

Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models

Authors: Kulkarni, Janardhan ; Li, Shi

Abstract | Document (520 KB) | BibTeX

Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices

Authors: Levi, Amit ; Yoshida, Yuichi

Abstract | Document (525 KB) | BibTeX

Deterministic Heavy Hitters with Sublinear Query Time

Authors: Li, Yi ; Nakos, Vasileios

Abstract | Document (546 KB) | BibTeX

On Low-Risk Heavy Hitters and Sparse Recovery Schemes

Authors: Li, Yi ; Nakos, Vasileios ; Woodruff, David P.

Abstract | Document (569 KB) | BibTeX

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut

Authors: Manurangsi, Pasin ; Trevisan, Luca

Abstract | Document (558 KB) | BibTeX

Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers

Authors: Narayanan, Shyam

Abstract | Document (476 KB) | BibTeX

Robust Online Speed Scaling With Deadline Uncertainty

Authors: Reddy, Goonwanth ; Vaze, Rahul

Abstract | Document (517 KB) | BibTeX

Multi-Agent Submodular Optimization

Authors: Santiago, Richard ; Shepherd, F. Bruce

Abstract | Document (588 KB) | BibTeX

Generalized Assignment of Time-Sensitive Item Groups

Authors: Sarpatwar, Kanthi ; Schieber, Baruch ; Shachnai, Hadas

Abstract | Document (508 KB) | BibTeX

On Geodesically Convex Formulations for the Brascamp-Lieb Constant

Authors: Sra, Suvrit ; Vishnoi, Nisheeth K. ; Yildiz, Ozan

Abstract | Document (425 KB) | BibTeX

Tensor Rank is Hard to Approximate

Authors: Swernofsky, Joseph

Abstract | Document (425 KB) | BibTeX

An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity

Authors: Wei, Hao-Ting ; Hon, Wing-Kai ; Horn, Paul ; Liao, Chung-Shou ; Sadakane, Kunihiko

Abstract | Document (513 KB) | BibTeX

Fixed-Parameter Approximation Schemes for Weighted Flowtime

Authors: Wiese, Andreas

Abstract | Document (504 KB) | BibTeX

List-Decoding Homomorphism Codes with Arbitrary Codomains

Authors: Babai, László ; Black, Timothy J. F. ; Wuu, Angela

Abstract | Document (570 KB) | BibTeX

Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources

Authors: Beigi, Salman ; Bogdanov, Andrej ; Etesami, Omid ; Guo, Siyao

Abstract | Document (446 KB) | BibTeX

Adaptive Lower Bound for Testing Monotonicity on the Line

Authors: Belovs, Aleksandrs

Abstract | Document (387 KB) | BibTeX

Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region

Authors: Blanca, Antonio ; Chen, Zongchen ; Vigoda, Eric

Abstract | Document (429 KB) | BibTeX

Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs

Authors: Blanca, Antonio ; Galanis, Andreas ; Goldberg, Leslie Ann ; Stefankovic, Daniel ; Vigoda, Eric ; Yang, Kuan

Abstract | Document (505 KB) | BibTeX

Polar Codes with Exponentially Small Error at Finite Block Length

Authors: Blasiok, Jaroslaw ; Guruswami, Venkatesan ; Sudan, Madhu

Abstract | Document (518 KB) | BibTeX

Approximate Degree and the Complexity of Depth Three Circuits

Authors: Bun, Mark ; Thaler, Justin

Abstract | Document (617 KB) | BibTeX

Speeding up Switch Markov Chains for Sampling Bipartite Graphs with Given Degree Sequence

Authors: Carstens, Corrie Jacobien ; Kleer, Pieter

Abstract | Document (487 KB) | BibTeX

Randomness Extraction in AC0 and with Small Locality

Authors: Cheng, Kuan ; Li, Xin

Abstract | Document (586 KB) | BibTeX

Boolean Function Analysis on High-Dimensional Expanders

Authors: Dikstein, Yotam ; Dinur, Irit ; Filmus, Yuval ; Harsha, Prahladh

Abstract | Document (510 KB) | BibTeX

Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents

Authors: Gracar, Peter ; Stauffer, Alexandre

Abstract | Document (1,510 KB) | BibTeX

Flipping out with Many Flips: Hardness of Testing k-Monotonicity

Authors: Grigorescu, Elena ; Kumar, Akash ; Wimmer, Karl

Abstract | Document (549 KB) | BibTeX

How Long Can Optimal Locally Repairable Codes Be?

Authors: Guruswami, Venkatesan ; Xing, Chaoping ; Yuan, Chen

Abstract | Document (495 KB) | BibTeX

On Minrank and Forbidden Subgraphs

Authors: Haviv, Ishay

Abstract | Document (421 KB) | BibTeX

Preserving Randomness for Adaptive Algorithms

Authors: Hoza, William M. ; Klivans, Adam R.

Abstract | Document (612 KB) | BibTeX

Commutative Algorithms Approximate the LLL-distribution

Authors: Iliopoulos, Fotis

Abstract | Document (537 KB) | BibTeX

The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree

Authors: Johansson, Tony

Abstract | Document (505 KB) | BibTeX

Satisfiability and Derandomization for Small Polynomial Threshold Circuits

Authors: Kabanets, Valentine ; Lu, Zhenjian

Abstract | Document (556 KB) | BibTeX

High Order Random Walks: Beyond Spectral Gap

Authors: Kaufman, Tali ; Oppenheim, Izhar

Abstract | Document (454 KB) | BibTeX

Improved Composition Theorems for Functions and Relations

Authors: Koroth, Sajin ; Meir, Or

Abstract | Document (563 KB) | BibTeX

Round Complexity Versus Randomness Complexity in Interactive Proofs

Authors: Leshkowitz, Maya

Abstract | Document (492 KB) | BibTeX

Improved List-Decodability of Random Linear Binary Codes

Authors: Li, Ray ; Wootters, Mary

Abstract | Document (530 KB) | BibTeX

Sunflowers and Quasi-Sunflowers from Randomness Extractors

Authors: Li, Xin ; Lovett, Shachar ; Zhang, Jiapeng

Abstract | Document (473 KB) | BibTeX

Torpid Mixing of Markov Chains for the Six-vertex Model on Z^2

Authors: Liu, Tianyu

Abstract | Document (4,290 KB) | BibTeX

On the Testability of Graph Partition Properties

Authors: Nakar, Yonatan ; Ron, Dana

Abstract | Document (513 KB) | BibTeX

On Closeness to k-Wise Uniformity

Authors: O'Donnell, Ryan ; Zhao, Yu

Abstract | Document (520 KB) | BibTeX

Pseudo-Derandomizing Learning and Approximation

Authors: Carboni Oliveira, Igor ; Santhanam, Rahul

Abstract | Document (519 KB) | BibTeX

Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits

Authors: Servedio, Rocco A. ; Tan, Li-Yang

Abstract | Document (687 KB) | BibTeX

Randomly Coloring Graphs of Logarithmically Bounded Pathwidth

Authors: Vardi, Shai

Abstract | Document (516 KB) | BibTeX

Explicit Strong LTCs with Inverse Poly-Log Rate and Constant Soundness

Authors: Viderman, Michael

Abstract | Document (469 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)