Program Chairs

David Steurer
Cornell, USA

Eric Blais
University of Waterloo, Canada

Workshop Chairs

José Rolim,
University of Geneva
Klaus Jansen,
University of Kiel

Program Committee


Parinya Chalermsook (Aalto)
Alina Ene (BU)
Fabrizio Grandoni (IDSIA)
Anupam Gupta (CMU)
Pravesh Kothari (Princeton and IAS)
Lap Chi Lau (Waterloo)
Euiwoong Lee (Simons Institute)
James Lee (UW)
Edo Liberty (Amazon)
Yury Makarychev (TTI)
Neil Olver (Amsterdam)
Yuval Rabani (HUJI)
Tselil Schramm (Harvard and MIT)
Roy Schwartz (Technion)
Noah Stephens-Davidowitz (Princeton)
David Steurer (ETH)
Inbal Talgam-Cohen (HUJI)
Aravindan Vijayaraghavan (Northwestern)
Justin Ward (Queens Mary)
Tony Wirth (Melbourne)
Grigory Yaroslavtsev (Indiana)


Eric Blais (U. Waterloo)
Joshua Brody (Swarthmore College)
Xi Chen (Columbia U.)
Gil Cohen (Princeton and Tel Aviv U.)
Andrew Drucker (U. Chicago)
Tom Gur (UC Berkeley)
Daniel Kane (UCSD)
Pravesh Kothari (Princeton U. and IAS)
Reut Levi (Weizmann Institute)
Aleksandar Nikolov (U. Toronto)
Lev Reyzin (U. Illinois Chicago)
Noga Ron-Zewi (Haifa U.)
Ron Rosenthal (Technion)
Atri Rudra (U. Buffalo)
Or Sheffet (U. Alberta)
Thomas Watson (U. Memphis)
Yuichi Yoshida (NII)
Important dates
Submission deadline
Friday, April 20, 2018
15:00 PDT

Notification to authors
By June 1, 2018

Camera ready
June 11, 2018

August 20-22, 2018
Call for papers
Accepted Papers
RANDOM 2018 Accepted Papers

RANDOM 2018 Accepted Papers

Michael Viderman. Explicit Strong LTCs with inverse poly-log rate and constant soundness
Maya Leshkowitz. Round Complexity Versus Randomness Complexity in Interactive Proofs
Tali Kaufman and Izhar Oppenhein. High Order Random Walks: Beyond Spectral Gap
Yonatan Nakar and Dana Ron. On the Testability of Graph Partition Properties
Tianyu Liu. Torpid Mixing of Markov Chains for the Six-vertex Model on Z2
William Hoza and Adam Klivans. Preserving Randomness for Adaptive Algorithms
Peter Gracar and Alexandre Stauffer. Percolation of Lipschitz surface and tight bounds on the spread of information among mobile agents
Ishay Haviv. On Minrank and Forbidden Subgraphs
Shai Vardi. Randomly coloring graphs of logarithmically bounded pathwidth
Ryan O'Donnell and Yu Zhao. On closeness to k-wise uniformity
Pieter Kleer and Corrie Jacobien Carstens. Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence
Rocco Servedio and Li-Yang Tan. Luby-Velickovic-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
Venkatesan Guruswami, Chaoping Xing and Chen Yuan. How long can optimal locally repairable codes be?
Elena Grigorescu, Akash Kumar and Karl Wimmer. Flipping out with many flips: hardness of testing k-monotonicity
Ray Li and Mary Wootters. Improved list-decodability of random linear binary codes
Fotis Iliopoulos. Commutative Algorithms Approximate the LLL distribution
Xin Li, Shachar Lovett and Jiapeng Zhang. Sunflowers and Quasi-sunflowers from Randomness Extractors
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda and Kuan Yang. Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
Valentine Kabanets and Zhenjian Lu. Satisfiability and Derandomization for Small Polynomial Threshold Circuits
Kuan Cheng and Xin Li. Randomness Extraction in AC0 and with Small Locality
Aleksandrs Belovs. Adaptive Lower Bound for Testing Monotonicity on the Line
Igor Oliveira and Rahul Santhanam. Pseudo-derandomizing learning and approximation
Tony Johansson. The cover time of a biased random walk on a random regular graph of odd degree
Mark Bun and Justin Thaler. Approximate Degree and the Complexity of Depth Three Circuits
Sajin Koroth and Or Meir. Improved composition theorems for functions and relations
Salman Beigi, Andrej Bogdanov, Omid Etesami and Siyao Guo. Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources
Yotam Dickstein, Irit Dinur, Yuval Filmus and Prahladh Harsha. Boolean function analysis on high-dimensional expanders
Antonio Blanca, Zongchen Chen and Eric Vigoda. Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region
Jaroslaw Blasiok, Venkatesan Guruswami and Madhu Sudan. Polar codes with exponentially small error at finite block length
Laszlo Babai, Timothy Black and Angela Wuu. List-decoding homomorphism codes with arbitrary codomains

APPROX 2018 Accepted Papers

APPROX 2018 Accepted Papers

Ishay Haviv. On Minrank and the Lovasz Theta Function
Goonwanth Reddy and Rahul Vaze. Robust Online Speed Scaling With Deadline Uncertainty
Amit Levi and Yuichi Yoshida. Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices
Mark Braverman and Young Kun Ko. Semi-Direct Sum Theorem and Nearest Neighbor under l infinity
Andreas Wiese. Fixed-parameter approximation schemes for weighted flowtime
Joseph Swernofsky. Tensor Rank is Hard to Approximate
Allan Borodin, Christodoulos Karavasilis and Denis Pankratov. Greedy Bipartite Matching in Random Type Poisson Arrival Model
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi. Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems
Yi Li and Vasileios Nakos. Deterministic Heavy Hitters with Sublinear Query Time
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu and Yuhao Zhang. Online Makespan Minimization: The Power of Restart
Talya Eden and Will Rosenbaum. Lower Bounds for Approximating Graph Parameters via Communication Complexity
Pasin Manurangsi and Luca Trevisan. Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
Janardhan Kulkarni and Shi Li. Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models
Suvrit Sra, Nisheeth K. Vishnoi and Ozan Yıldız. On Geodesically Convex Formulations for the Brascamp-Lieb Constant
Hao-Ting Wei, Wing-Kai Hon, Paul Horn, Chung-Shou Liao and Kunihiko Sadakane. An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity
Eden Chlamtac and Pasin Manurangsi. Sherali-Adams Integrality Gaps Matching the Log-Density Threshold
Vladimir Braverman, Elena Grigorescu, Harry Lang, David Woodruff and Samson Zhou. Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
Anat Ganor and Karthik C. S.. Communication Complexity of Correlated Equilibrium with Small Support
Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit and Daniel Vaz. Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
Vasileios Nakos, Yi Li and David Woodruff. On Low-Risk Heavy Hitters and Sparse Recovery Schemes
Chandra Chekuri and Shalmoli Gupta. Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations
Kanthi Sarpatwar, Baruch Schieber and Hadas Shachnai. Generalized Assignment of Time-Sensitive Item Groups
Richard Santiago and F. Bruce Shepherd. Multi-Agent Submodular Optimization
Sayan Bandyapadhyay, Neeraj Kumar, Subhash Suri and Kasturi Varadarajan. Improved Approximation Bounds for the Minimum Constraint Removal Problem
Aditya Krishnan, Sidhanth Mohanty and David P. Woodruff. On Sketching the q to p Norms
Aditya Bhaskara and Srivatsan Kumar. Low Rank Approximation in the Presence of Outliers
Amariah Becker. A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees
Shyam Narayanan. Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers

Valid XHTML 1.0 Transitional Valid CSS!

Created by Marios Karagiannis - Maintained by Stephane Kundig