Portal - APPROX/RANDOM 2015

APPROX/RANDOM 2015	August 24-26, 2015 - Princeton, USA
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) Naveen Garg and Klaus Jansen and Anup Rao and José D. P. Rolim (Eds.)
ISBN 978-3-939897-89-7, LIPICS Vol. 40	ISSN 1868-8969

Additional Information

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

Authors

Bhattiprolu, Vijay V. S. P.

Blais, Eric

Blanca, Antonio

Bottesch, Ralph Christian

Fichtenberger, Hendrik

Guruswami, Venkatesan

Haeupler, Bernhard

Harris, David G.

Harvey, Nicholas J. A.

Kasiviswanathan, Shiva Prasad

Krishnaswamy, Ravishankar

Racicot-Desloges, David

Saptharishi, Ramprasad

Vijayaraghavan, Aravindan

Frontmatter, Table of Contents, Preface, Program Commitees, External Reviewers, List of Authors

Authors: Garg, Naveen ; Jansen, Klaus ; Rao, Anup ; Rolim, José D. P.

Abstract | Document (353 KB) | BibTeX

On Guillotine Cutting Sequences

Authors: Abed, Fidaa ; Chalermsook, Parinya ; Correa, José ; Karrenbauer, Andreas ; Pérez-Lantero, Pablo ; Soto, José A. ; Wiese, Andreas

Abstract | Document (545 KB) | BibTeX

Approximate Nearest Neighbor Search in Metrics of Planar Graphs

Authors: Abraham, Ittai ; Chechik, Shiri ; Krauthgamer, Robert ; Wieder, Udi

Abstract | Document (687 KB) | BibTeX

How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking

Authors: Adamaszek, Anna ; Chalermsook, Parinya ; Wiese, Andreas

Abstract | Document (584 KB) | BibTeX

Non-Uniform Robust Network Design in Planar Graphs

Authors: Adjiashvili, David

Abstract | Document (486 KB) | BibTeX

Large Supports are Required for Well-Supported Nash Equilibria

Authors: Anbalagan, Yogesh ; Huang, Hao ; Lovett, Shachar ; Norin, Sergey ; Vetta, Adrian ; Wu, Hehui

Abstract | Document (441 KB) | BibTeX

Minimizing Maximum Flow-time on Related Machines

Authors: Bansal, Nikhil ; Cloostermans, Bouke

Abstract | Document (427 KB) | BibTeX

A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs

Authors: Bansal, Nikhil ; Gupta, Anupam ; Krishnaswamy, Ravishankar ; Pruhs, Kirk ; Schewior, Kevin ; Stein, Cliff

Abstract | Document (500 KB) | BibTeX

Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree

Authors: Barak, Boaz ; Moitra, Ankur ; O’Donnell, Ryan ; Raghavendra, Prasad ; Regev, Oded ; Steurer, David ; Trevisan, Luca ; Vijayaraghavan, Aravindan ; Witmer, David ; Wright, John

Abstract | Document (520 KB) | BibTeX

Improved Bounds in Stochastic Matching and Optimization

Authors: Baveja, Alok ; Chavan, Amit ; Nikiforov, Andrei ; Srinivasan, Aravind ; Xu, Pan

Abstract | Document (483 KB) | BibTeX

Fully Dynamic Bin Packing Revisited

Authors: Berndt, Sebastian ; Jansen, Klaus ; Klein, Kim-Manuel

Abstract | Document (638 KB) | BibTeX

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises

Authors: Bhattiprolu, Vijay V. S. P. ; Guruswami, Venkatesan ; Lee, Euiwoong

Abstract | Document (596 KB) | BibTeX

Stochastic and Robust Scheduling in the Cloud

Authors: Chen, Lin ; Megow, Nicole ; Rischke, Roman ; Stougie, Leen

Abstract | Document (491 KB) | BibTeX

On Approximating Node-Disjoint Paths in Grids

Authors: Chuzhoy, Julia ; Kim, David H. K.

Abstract | Document (1,778 KB) | BibTeX

Approximating Upper Degree-Constrained Partial Orientations

Authors: Cygan, Marek ; Kociumaka, Tomasz

Abstract | Document (478 KB) | BibTeX

Approximating Hit Rate Curves using Streaming Algorithms

Authors: Drudi, Zachary ; Harvey, Nicholas J. A. ; Ingram, Stephen ; Warfield, Andrew ; Wires, Jake

Abstract | Document (538 KB) | BibTeX

Terminal Embeddings

Authors: Elkin, Michael ; Filtser, Arnold ; Neiman, Ofer

Abstract | Document (638 KB) | BibTeX

On Linear Programming Relaxations for Unsplittable Flow in Trees

Authors: Friggstad, Zachary ; Gao, Zhihan

Abstract | Document (562 KB) | BibTeX

Inapproximability of H-Transversal/Packing

Authors: Guruswami, Venkatesan ; Lee, Euiwoong

Abstract | Document (707 KB) | BibTeX

Towards a Characterization of Approximation Resistance for Symmetric CSPs

Authors: Guruswami, Venkatesan ; Lee, Euiwoong

Abstract | Document (550 KB) | BibTeX

Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs

Authors: Harris, David G. ; Sullivan, Francis

Abstract | Document (482 KB) | BibTeX

Improved NP-Inapproximability for 2-Variable Linear Equations

Authors: Håstad, Johan ; Huang, Sangxia ; Manokaran, Rajsekar ; O’Donnell, Ryan ; Wright, John

Abstract | Document (567 KB) | BibTeX

A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties

Authors: Huang, Chien-Chung ; Iwama, Kazuo ; Miyazaki, Shuichi ; Yanagisawa, Hiroki

Abstract | Document (545 KB) | BibTeX

Designing Overlapping Networks for Publish-Subscribe Systems

Authors: Iglesias, Jennifer ; Rajaraman, Rajmohan ; Ravi, R. ; Sundaram, Ravi

Abstract | Document (525 KB) | BibTeX

Approximating Dense Max 2-CSPs

Authors: Manurangsi, Pasin ; Moshkovitz, Dana

Abstract | Document (530 KB) | BibTeX

The Container Selection Problem

Authors: Nagarajan, Viswanath ; Sarpatwar, Kanthi K. ; Schieber, Baruch ; Shachnai, Hadas ; Wolf, Joel L.

Abstract | Document (668 KB) | BibTeX

Tight Bounds for Graph Problems in Insertion Streams

Authors: Sun, Xiaoming ; Woodruff, David P.

Abstract | Document (475 KB) | BibTeX

A Chasm Between Identity and Equivalence Testing with Conditional Queries

Authors: Acharya, Jayadev ; Canonne, Clément L. ; Kamath, Gautam

Abstract | Document (617 KB) | BibTeX

Harnessing the Bethe Free Energy

Authors: Bapst, Victor ; Coja-Oghlan, Amin

Abstract | Document (553 KB) | BibTeX

Internal Compression of Protocols to Entropy

Authors: Bauer, Balthazar ; Moran, Shay ; Yehudayoff, Amir

Abstract | Document (491 KB) | BibTeX

On Fortification of Projection Games

Authors: Bhangale, Amey ; Saptharishi, Ramprasad ; Varma, Girish ; Venkat, Rakesh

Abstract | Document (539 KB) | BibTeX

Learning Circuits with few Negations

Authors: Blais, Eric ; Canonne, Clément L. ; Oliveira, Igor C. ; Servedio, Rocco A. ; Tan, Li-Yang

Abstract | Document (547 KB) | BibTeX

Dynamics for the Mean-field Random-cluster Model

Authors: Blanca, Antonio ; Sinclair, Alistair

Abstract | Document (586 KB) | BibTeX

Correlation in Hard Distributions in Communication Complexity

Authors: Bottesch, Ralph Christian ; Gavinsky, Dmitry ; Klauck, Hartmut

Abstract | Document (614 KB) | BibTeX

Zero-One Laws for Sliding Windows and Universal Sketches

Authors: Braverman, Vladimir ; Ostrovsky, Rafail ; Roytman, Alan

Abstract | Document (568 KB) | BibTeX

Universal Sketches for the Frequency Negative Moments and Other Decreasing Streaming Sums

Authors: Braverman, Vladimir ; Chestnut, Stephen R.

Abstract | Document (539 KB) | BibTeX

Dependent Random Graphs and Multi-Party Pointer Jumping

Authors: Brody, Joshua ; Sanchez, Mario

Abstract | Document (576 KB) | BibTeX

Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

Authors: Bun, Mark ; Steinke, Thomas

Abstract | Document (542 KB) | BibTeX

Tighter Connections between Derandomization and Circuit Lower Bounds

Authors: Carmosino, Marco L. ; Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina

Abstract | Document (535 KB) | BibTeX

Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees

Authors: Chechik, Shiri ; Cohen, Edith ; Kaplan, Haim

Abstract | Document (582 KB) | BibTeX

Two Structural Results for Low Degree Polynomials and Applications

Authors: Cohen, Gil ; Tal, Avishay

Abstract | Document (634 KB) | BibTeX

The Minimum Bisection in the Planted Bisection Model

Authors: Coja-Oghlan, Amin ; Cooley, Oliver ; Kang, Mihyun ; Skubch, Kathrin

Abstract | Document (510 KB) | BibTeX

Local Convergence of Random Graph Colorings

Authors: Coja-Oghlan, Amin ; Efthymiou, Charilaos ; Jaafari, Nor

Abstract | Document (482 KB) | BibTeX

Towards Resistance Sparsifiers

Authors: Dinitz, Michael ; Krauthgamer, Robert ; Wagner, Tal

Abstract | Document (538 KB) | BibTeX

Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees

Authors: Efthymiou, Charilaos

Abstract | Document (518 KB) | BibTeX

A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words

Authors: Felber, David ; Ostrovsky, Rafail

Abstract | Document (515 KB) | BibTeX

On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs

Authors: Fichtenberger, Hendrik ; Peng, Pan ; Sohler, Christian

Abstract | Document (524 KB) | BibTeX

Dimension Expanders via Rank Condensers

Authors: Forbes, Michael A. ; Guruswami, Venkatesan

Abstract | Document (530 KB) | BibTeX

Swendsen-Wang Algorithm on the Mean-Field Potts Model

Authors: Galanis, Andreas ; Štefankovic, Daniel ; Vigoda, Eric

Abstract | Document (610 KB) | BibTeX

Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms

Authors: Ge, Rong ; Ma, Tengyu

Abstract | Document (518 KB) | BibTeX

Negation-Limited Formulas

Authors: Guo, Siyao ; Komargodski, Ilan

Abstract | Document (579 KB) | BibTeX

Deletion Codes in the High-noise and High-rate Regimes

Authors: Guruswami, Venkatesan ; Wang, Carol

Abstract | Document (446 KB) | BibTeX

Communication with Partial Noiseless Feedback

Authors: Haeupler, Bernhard ; Kamath, Pritish ; Velingker, Ameya

Abstract | Document (519 KB) | BibTeX

Spectral Norm of Random Kernel Matrices with Applications to Privacy

Authors: Kasiviswanathan, Shiva Prasad ; Rudelson, Mark

Abstract | Document (597 KB) | BibTeX

Separating Decision Tree Complexity from Subcube Partition Complexity

Authors: Kothari, Robin ; Racicot-Desloges, David ; Santha, Miklos

Abstract | Document (516 KB) | BibTeX

Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent

Authors: Mossel, Elchanan ; Roch, Sebastien

Abstract | Document (1,781 KB) | BibTeX

Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials

Authors: Volkovich, Ilya

Abstract | Document (533 KB) | BibTeX

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

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