|
Accepted papers in Random - Papers
- A Chasm Between Identity and Equivalence Testing with Conditional Queries Jayadev Acharya, Clément Canonne and Gautam Kamath
- Dynamics for the mean-field random-cluster model Antonio Blanca and Alistair Sinclair
- The minimum bisection in the planted bisection model Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang and Kathrin Skubch
- Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares AlgorithmsRong Ge and Tengyu Ma
- Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees Shiri Chechik, Edith Cohen and Haim Kaplan
- Learning circuits with few negations Eric Blais, Clément Canonne, Igor Carboni Oliveira, Rocco Servedio and Li-Yang Tan
- Separating decision tree complexity from subcube partition complexity Robin Kothari, David Racicot-Desloges and Miklos Santha
- Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials Ilya Volkovich
- Swendsen-Wang Algorithm on the Mean-Field Potts Model Andreas Galanis, Daniel Stefankovic and Eric Vigoda
- Harnessing the Bethe free energy Victor Bapst and Amin Coja-Oghlan
- Zero-One Laws for Sliding Windows and Universal Sketches Vladimir Braverman, Rafail Ostrovsky and Alan Roytman
- Spectral Norm of Random Kernel Matrices with Applications to Privacy Shiva Kasiviswanathan and Mark Rudelson
- Distance-based species tree estimation: information-theoretic trade-off between number of loci and sequence length under the coalescent Elchanan Mossel and Sebastien Roch
- A randomized online quantile summary in $O(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$ words David Felber and Rafail Ostrovsky
- Two Structural Results for Low Degree Polynomials and Applications Gil Cohen and Avishay Tal
- Local convergence of random graph colorings Amin Coja-Oghlan, Charilaos Efthymiou and Nor Jaafari
- Tighter Connections between Derandomization and Circuit Lower Bounds Marco Carmosino, Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova
- Correlation in Hard Distributions in Communication Complexity Dmitry Gavinsky, Hartmut Klauck and Ralph Bottesch
- Communication with partial noiseless feedback Bernhard Haeupler, Pritish Kamath and Ameya Velingker
- On Constant Size Graphs That Preserve the Local Structure of High Girth Graphs Hendrik Fichtenberger, Pan Peng and Christian Sohler
- Dimension Expanders via Rank Condensers Michael A. Forbes and Venkatesan Guruswami
- Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness Mark Bun and Thomas Steinke
- 24. Internal compression of protocols to entropy Shay Moran, Amir Yehudayoff and Balthazar Bauer
- Deletion codes in the high-noise and high-rate regimes Venkatesan Guruswami and Carol Wang
- Towards Resistance Sparsifiers Michael Dinitz, Robert Krauthgamer and Tal Wagner
- Universal sketches for the frequency negative moments and other decreasing streaming sums Stephen Chestnut and Vladimir Braverman
- Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees Charilaos Efthymiou
- On Fortification of Projection Games Amey Bhangale, Ramprasad Saptharishi, Girish Varma and Rakesh Venkat
- Negation-Limited Formulas Siyao Guo and Ilan Komargodski
- Dependent Random Graphs and Multiparty Pointer JumpingJoshua Brody and Mario Sanchez
Accepted papers in Approx - Papers
- Improved NP-inapproximability for 2-variable linear equations Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell and John Wright
- On Linear Programming Relaxations for Unsplittable Flow in Trees Zachary Friggstad and Zhihan Gao
- Fully Dynamic Bin Packing Revisited Sebastian Berndt, Klaus Jansen and Kim-Manuel Klein
- Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs David Harris and Francis Sullivan
- Inapproximability of H-Transversal/Packing Venkatesan Guruswami and Euiwoong Lee
- On Approximating Node-Disjoint Paths in Grids Julia Chuzhoy and David Kim
- Large Supports are required for Well-Supported Nash Equilibria Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta and Hehui Wu
- Approximate Nearest Neighbor Search in Metrics of Planar Graphs Ittai Abraham, Shiri Chechik, Robert Krauthgamer and Udi Wieder
- Terminal Embeddings Michael Elkin, Arnold Filtser and Ofer Neiman
- Stochastic and Robust Scheduling in the Cloud Lin Chen, Nicole Megow, Roman Rischke and Leen Stougie
- Towards a Characterization of Approximation Resistance for Symmetric CSPs Venkatesan Guruswami and Euiwoong Lee.
- Improved Bounds in Stochastic Matching and Optimization Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan and Pan Xu
- The Container Selection Problem Viswanath Nagarajan, Kanthi Sarpatwar, Baruch Schieber, Hadas Shachnai and Joel Wolf
- Approximating Hit Rate Curves using Streaming Algorithms Zachary Drudi, Nicholas Harvey, Stephen Ingram, Andrew Warfield and Jake Wires
- How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking Anna Adamaszek, Parinya Chalermsook and Andreas Wiese
- On guillotine cutting sequences Fidaa Abed, Parinya Chalermsook, Jose Correa, Andreas Karrenbauer, Pablo Perez-Lantero, Jose Soto and Andreas Wiese
- Minimizing maximum flow-time on related machines Bouke Cloostermans and Nikhil Bansal
- A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa
- A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior and Clifford Stein
- Designing Overlapping Networks for Publish-Subscribe Systems Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi and Ravi Sundaram
- Tight Bounds for Graph Problems in Insertion Streams Xiaoming Sun and David Woodruff
- Approximating Upper Degree-Constrained Partial Orientations Marek Cygan and Tomasz Kociumaka
- Approximating Dense Max 2-CSPs Pasin Manurangsi and Dana Moshkovitz
- Beating the random assignment on constraint satisfaction problems of bounded degreeBoaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer and John Wright
- Approximate Hypergraph Coloring under Low-discrepancy and Related PromisesV.S.P. Vijay Bhattiprolu, Venkatesan Guruswami and Euiwoong Lee
- Non-Uniform Robust Network Design in Planar GraphsDavid Adjiashvili
|
PDF Format
doc
txt
