|
Accepted papers in Random - Papers
- Combinatorial limitations of average-radius list decoding Venkatesan Guruswami and Srivatsan Narayanan.
- Fast Private Data Release Algorithms for Sparse Queries Avrim Blum and Aaron Roth.
- What you can do with Coordinated Samples Edith Cohen and Haim Kaplan.
- Local reconstructors and tolerant testers for connectivity and diameter Andrea Campagna, Alan Guo and Ronitt Rubinfeld.
- Testing Membership in Counter Automaton Languages Yonatan Goldhirsh and Michael Viderman.
- Absolutely Sound Testing of Lifted Codes Noga Ron-Zewi, Elad Haramaty and Madhu Sudan.
- Randomness-Efficient Curve Samplers Zeyu Guo.
- Matching-Vector Families and LDCs Over Large Modulo Zeev Dvir and Guangda Hu.
- An optimal lower bound for monotonicity testing over hypergrids Deeparnab Chakrabarty and C. Seshadhri.
- Zero Knowledge LTCs and Their Applications Yuval Ishai, Amit Sahai, Michael Viderman and Mor Weiss.
- Improved FPTAS for Multi-Spin Systems Pinyan Lu and Yitong Yin.
- Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions Juan Vera, Eric Vigoda and Linji Yang.
- Connectivity of Random High Dimensional Geometric Graphs Roee David and Uriel Feige.
- Phase Coexistence and Slow Mixing for the Hard-Core Model on Z^2 Antonio Blanca, David Galvin, Dana Randall and Prasad Tetali.
- Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing Michael A. Forbes and Amir Shpilka.
- The Power of Choice for Random Satisfiability Varsha Dani, Josep Diaz, Thomas Hayes and Cristopher Moore.
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy Amos Beimel, Kobbi Nissim and Uri Stemmer.
- Finding Heavy Hitters from Partial or Noisy Data Lucia Batman, Russell Impagliazzo, Cody Murray and Ramamohan Paturi.
- On the average sensitivity and density of k-CNF formulas Dominik Scheder and Li-Yang Tan.
- Robust Randomness Amplifiers: Upper and Lower Bounds Matthew Coudron, Thomas Vidick and Henry Yuen.
- A Tight Lower Bound for High Frequency Moment Estimation with Small Error Yi Li and David Woodruff.
- Tight lower bounds for testing linear isomorphism Elena Grigorescu, Karl Wimmer and Ning Xie.
- Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem Sixia Chen, Cristopher Moore and Alexander Russell.
- Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration Emmanuel Abbe and Andrea Montanari.
- Pseudorandomness for Regular Branching Programs via Fourier Analysis Omer Reingold, Thomas Steinke and Salil Vadhan.
Accepted papers in Approx - Papers
- Improved Hardness of Approximating Chromatic Number Sangxia Huang
- Sketching Earth-Mover Distance on Graph Metrics Andrew McGregor and Daniel Stubbs
- Online Square-into-Square Packing Sandor Fekete and Hella-Franziska Hoffmann
- Scheduling Subset Tests: One-time, Continuous, and How They Relate Edith Cohen, Haim Kaplan and Yishay Mansour
- Partial Interval Set Cover Trade-offs Between Scalability and Optimality Katherine Edwards, William Kennedy and Simon Griffiths
- Approximation Algorithms for Movement Repairmen Mohammadtaghi Hajiaghayi, Rohit Khandekar, Reza Khani and Guy Kortsarz
- The Approximability of the Binary Paintshop Problem Anupam Gupta, Satyen Kale, Viswanath Nagarajan, Rishi Saket and Baruch Schieber
- Spectral Sparsification in Dynamic Graph Streams Kook Jin Ahn, Sudipto Guha and Andrew McGregor
- Capacitated Network Design on Undirected Graphs Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Shi Li and Srivatsan Narayanan
- On the total perimeter of homothetic convex bodies in a convex container Adrian Dumitrescu and Csaba Toth
- A pseudo-approximation for the genus of Hamiltonian graphs Yury Makarychev, Amir Nayyeri and Anastasios Sidiropoulos
- A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs Shayan Oveis Gharan and Luca Trevisan
- Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams Vladimir Braverman and Rafail Ostrovsky
- Approximating Large Frequency Moments with Pick-and-Drop Sampling Vladimir Braverman and Rafail Ostrovsky
- Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback Sudipto Guha and Kamesh Munagala
- On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems Per Austrin, Rajsekar Manokaran and Cenny Wenner
- Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions Kyle Fox, Sungjin Im, Janardhan Kulkarni and Benjamin Moseley
- Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems Pierre Fraigniaud, Magnus M. Halldorsson, Boaz Patt-Shamir, Dror Rawitz and Adi Rosen
- A local computation approximation scheme to maximum matching Yishay Mansour and Shai Vardi
- Multiple Traveling Salesmen in Asymmetric Metrics Zachary Friggstad
- The Online Stochastic Generalized Assignment Problem Saeed Alaei, Mohammadtaghi Hajiaghayi and Vahid Liaghat
- Interdiction Problems on Planar Graphs Feng Pan and Aaron Schild
- Online Multidimensional Load Balancing Adam Meyerson, Alan Roytman and Brian Tagiku
|
PDF Format
Plain Text
