Navigation

Program Chairs


APPROX
David Steurer
Cornell, USA
dsteurer@cs.cornell.edu

RANDOM
Eric Blais
University of Waterloo, Canada
eric.blais@uwaterloo.ca

Workshop Chairs


José Rolim,
University of Geneva
jose.rolim@unige.ch
Klaus Jansen,
University of Kiel
kj@informatik.uni-kiel.de

Program Committee


APPROX

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)

RANDOM

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

Conference
August 20-22, 2018
Call for papers

Program

    APPROX + RANDOM 2018 Program

    Friend Center Lecture Hall 101


      Monday August 20

      8:00-8:30 Registration

      8:30-10:10 Session 1 (RANDOM):

    • Igor Oliveira and Rahul Santhanam - Pseudo-derandomizing learning and approximation.
    • William Hoza and Adam Klivans - Preserving Randomness for Adaptive Algorithms.
    • 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.
    • Xin Li, Shachar Lovett and Jiapeng Zhang - Sunflowers and Quasi-sunflowers from Randomness Extractors.

    • 10:10-10:30 Coffee Break

      10:30-12:10 Session 2 (APPROX):

    • Chandra Chekuri and Shalmoli Gupta - Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations.
    • Shyam Narayana - Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers.
    • Mark Braverman and Young Kun Ko - Semi-Direct Sum Theorem and Nearest Neighbor under l infinity.
    • Talya Eden and Will Rosenbaum - Lower Bounds for Approximating Graph Parameters via Communication Complexity.
    • Anat Ganor and Karthik C. S. - Communication Complexity of Correlated Equilibrium with Small Support.

    • 12:10-13:30 Lunch break

      13:30 - 15:10 Session 3 (RANDOM):

    • Shai Vard - Randomly coloring graphs of logarithmically bounded pathwidth.
    • Ishay Haviv - On Minrank and Forbidden Subgraphs.
    • Fotis Iliopoulos - Commutative Algorithms Approximate the LLL distribution.
    • Tali Kaufman and Izhar Oppenhein - High Order Random Walks: Beyond Spectral Gap.
    • Tony Johansson - The cover time of a biased random walk on a random regular graph of odd degree.

    • 15:10-15:30 Coffee Break

      15:30 - 17:10 Session 4 (APPROX):

    • Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi - Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems.
    • Pasin Manurangsi and Luca Trevisan - Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut.
    • 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.
    • Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit and Daniel Vaz - Survivable Network Design for Group Connectivity in Low-Treewidth Graphs.
    • Amariah Becker - A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees.

    • 17:00-20:00 Reception

      Tuesday August 21


      8:30-10:10 Session 5 (APPROX):

    • Amit Levi and Yuichi Yoshida - Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices.
    • Yi Li and Vasileios Nakos - Deterministic Heavy Hitters with Sublinear Query Time.
    • Vladimir Braverman, Elena Grigorescu, Harry Lang, David Woodruff and Samson Zhou - Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.
    • Vasileios Nakos, Yi Li and David Woodruff - On Low-Risk Heavy Hitters and Sparse Recovery Schemes.
    • Aditya Krishnan, Sidhanth Mohanty and David P. Woodruff - On Sketching the q to p Norms.

    • 10:10-10:30 Coffee Break

      10:30-12:10 Session 6 (RANDOM):

    • Jaroslaw Blasiok, Venkatesan Guruswami and Madhu Sudan - Polar codes with exponentially small error at finite block length
    • Venkatesan Guruswami, Chaoping Xing and Chen Yuan - How long can optimal locally repairable codes be?
    • Ray Li and Mary Wootters - Improved list-decodability of random linear binary codes.
    • Michael Viderman - Explicit Strong LTCs with inverse poly-log rate and constant soundness.
    • Laszlo Babai, Timothy Black and Angela Wuu - List-decoding homomorphism codes with arbitrary codomains.

    • 12:10-13:30 Lunch break

      13:30 - 15:10 Session 7 (APPROX):

    • 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.
    • Goonwanth Reddy and Rahul Vaze - Robust Online Speed Scaling With Deadline Uncertainty.
    • Allan Borodin, Christodoulos Karavasilis and Denis Pankratov - Greedy Bipartite Matching in Random Type Poisson Arrival Model.
    • Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu and Yuhao Zhang - Online Makespan Minimization: The Power of Restart.

    • 15:10-15:30 Coffee Break

      15:30 - 16:20 Session 8: Invited talk by Ronitt Rubinfeld, MIT - Local algorithms for sparse connected subgraphs

      16:20 - 18:00 Session 9 (RANDOM):

    • Tianyu Liu - Torpid Mixing of Markov Chains for the Six-vertex Model on Z2.
    • Pieter Kleer and Corrie Jacobien Carstens - Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence.
    • Antonio Blanca et al. - Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs.
    • Peter Gracar and Alexandre Stauffer - Percolation of Lipschitz surface and tight bounds on the spread of information among mobile agents.
    • Antonio Blanca, Zongchen Chen and Eric Vigoda - Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region.

    • Wednesday August 22


      8:30-10:10 Session 10 (RANDOM):

    • Maya Leshkowitz - Round Complexity Versus Randomness Complexity in Interactive Proofs.
    • Aleksandrs Belovs - Adaptive Lower Bound for Testing Monotonicity on the Line.
    • Ryan O'Donnell and Yu Zhao - On closeness to k-wise uniformity.
    • Elena Grigorescu, Akash Kumar and Karl Wimmer - Flipping out with many flips: hardness of testing k-monotonicity.
    • Yonatan Nakar and Dana Ron - On the Testability of Graph Partition Properties.

    • 10:10-10:30 Coffee Break

      10:30-12:10 Session 11 (APPROX):

    • Ishay Haviv - On Minrank and the Lovasz Theta Function.
    • Eden Chlamtac and Pasin Manurangsi - Sherali-Adams Integrality Gaps Matching the Log-Density Threshold.
    • Joseph Swernofsky - Tensor Rank is Hard to Approximate.
    • Suvrit Sra, Nisheeth K. Vishnoi and Ozan Yıldız - On Geodesically Convex Formulations for the Brascamp-Lieb Constant.
    • Aditya Bhaskara and Srivatsan Kumar - Low Rank Approximation in the Presence of Outliers.

    • 12:10-13:30 Lunch break

      13:30 - 15:10 Session 12 (RANDOM):

    • Rocco Servedio and Li-Yang Tan - Luby-Velickovic-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits.
    • 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.
    • 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.

    • 15:10-15:30 Coffee Break

      15:30 - 16:20 Session 13: Invited talk by Subhash Khot, NYU (Title TBA)

      16:20 - 17:20 Session 14 (APPROX):

    • Andreas Wiese - Fixed-parameter approximation schemes for weighted flowtime.
    • Kanthi Sarpatwar, Baruch Schieber and Hadas Shachnai - Generalized Assignment of Time-Sensitive Item Groups.
    • Janardhan Kulkarni and Shi Li - Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models.


     




Valid XHTML 1.0 Transitional Valid CSS!

Created by Marios Karagiannis - Maintained by Stephane Kundig