CFP.pdf |
Accepted Papers
RANDOM 2018 Accepted PapersExplicit Strong LTCs with inverse poly-log rate and constant soundness Round Complexity Versus Randomness Complexity in Interactive Proofs High Order Random Walks: Beyond Spectral Gap On the Testability of Graph Partition Properties Torpid Mixing of Markov Chains for the Six-vertex Model on Z2 Preserving Randomness for Adaptive Algorithms Percolation of Lipschitz surface and tight bounds on the spread of information among mobile agents On Minrank and Forbidden Subgraphs Randomly coloring graphs of logarithmically bounded pathwidth On closeness to k-wise uniformity Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence Luby-Velickovic-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits How long can optimal locally repairable codes be? Flipping out with many flips: hardness of testing k-monotonicity Improved list-decodability of random linear binary codes Commutative Algorithms Approximate the LLL distribution Sunflowers and Quasi-sunflowers from Randomness Extractors Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs Satisfiability and Derandomization for Small Polynomial Threshold Circuits Randomness Extraction in AC0 and with Small Locality Adaptive Lower Bound for Testing Monotonicity on the Line Pseudo-derandomizing learning and approximation The cover time of a biased random walk on a random regular graph of odd degree Approximate Degree and the Complexity of Depth Three Circuits Improved composition theorems for functions and relations Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources Boolean function analysis on high-dimensional expanders Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region Polar codes with exponentially small error at finite block length List-decoding homomorphism codes with arbitrary codomains
APPROX 2018 Accepted PapersOn Minrank and the Lovasz Theta Function Robust Online Speed Scaling With Deadline Uncertainty Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices Semi-Direct Sum Theorem and Nearest Neighbor under l infinity Fixed-parameter approximation schemes for weighted flowtime Tensor Rank is Hard to Approximate Greedy Bipartite Matching in Random Type Poisson Arrival Model Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems Deterministic Heavy Hitters with Sublinear Query Time Online Makespan Minimization: The Power of Restart Lower Bounds for Approximating Graph Parameters via Communication Complexity Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models On Geodesically Convex Formulations for the Brascamp-Lieb Constant An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity Sherali-Adams Integrality Gaps Matching the Log-Density Threshold Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows Communication Complexity of Correlated Equilibrium with Small Support Survivable Network Design for Group Connectivity in Low-Treewidth Graphs On Low-Risk Heavy Hitters and Sparse Recovery Schemes Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations Generalized Assignment of Time-Sensitive Item Groups Multi-Agent Submodular Optimization Improved Approximation Bounds for the Minimum Constraint Removal Problem On Sketching the q to p Norms Low Rank Approximation in the Presence of Outliers A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers
|
Navigation | ||
Program Chairs  APPROX David Steurer ETH, Zurich dsteurer@inf.ethz.ch 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 | ||