|
Accepted papers in Random - Papers
- Van Vu and Terence Tao. Smooth analysis of the condition number and the least singular value
- Oded Goldreich and Dana Ron. Algorithmic Aspects of Property Testing in The Dense Graphs Model
- Oded Goldreich, Michael Krivelevich, Ilan Newman and Eyal Rozenberg. Hierarchy Theorems for Property Testing
- Alan Frieze, Pall Melsted and Michael Mitzenmacher. An Analysis of Random-Walk Cuckoo Hashing
- Lorenz Minder and Danny Vilenchik. Small clique detection and approximate Nash equilibria
- Ido Ben Eliezer, Rani Hod and Shachar Lovett. Random low degree polynomials are hard to approximate
- Prasad Chebolu, Alan Frieze, Pall Melsted and Gregory Sorkin. Average-case analyses of Vickrey costs
- Dana Ron and Gilad Tsur. Testing Computability by Width Two OBDDs
- Adam Klivans, Philip Long and Alex Tang. Baum's Algorithm Learns Intersections of Halfspaces with respect to Log-Concave Distributions
- Victor Chen. A Hypergraph Dictatorship Test with Perfect Completeness
- Eli Ben-Sasson and Michael Viderman. Composition of semi-LTCs by two-wise Tensor Products
- Klim Efremenko and Omer Reingold. How Well Do Random Walks Parallelize?
- Amir Shpilka and Ilya Volkovich. Improved Polynomial Identity Testing for Read-Once Formulas
- Ricky Rosen, Ran Raz, Boaz Barak, Anup Rao and Ronen Shaltiel. Strong Parallel Repetition Theorem for Free Projection Games
- Elena Grigorescu, Tali Kaufman and Madhu Sudan. Succinct Representation of Codes with Applications to Testing
- Noga Alon, Rina Panigrahy and Sergey Yekhanin. Deterministic Approximation Algorithms for the Nearest Codeword Problem
- Andrej Bogdanov and Youming Qiao. On the Security of Goldreich's One-Way Function
- Brendan Lucier, Michael Molloy and Yuval Peres. The Glauber dynamics for colourings of bounded degree trees
- S. Charles Brubaker and Santosh Vempala. Random Tensors and Planted Cliques
- Aram Harrow and Richard Low. Efficient Quantum Tensor Product Expanders and k-designs
- Jeff Kinne, Dieter van Melkebeek and Ronen Shaltiel. Pseudorandom Generators and Typically-Correct Derandomization
- Shachar Lovett, Omer Reingold, Luca Trevisan and Salil Vadhan. Pseudorandom Bit Generators that Fool Modular Sums
- Karthekeyan Chandrasekaran, Amit Deshpande and Santosh Vempala. Sampling Harmonic Concave Functions: The Limit of Convexity Based Isoperimetry
- Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld and Rocco Servedio. Testing {-1,1}-Weight Halfspaces
- Raghu Meka and David Zuckerman. Small-Bias Spaces for Group Products
- Anindya De and Luca Trevisan. Extractors using hardness amplification
- T.S. Jayram. Hellinger Strikes Back: A Note on the Multi-Party Information Complexity of AND
- Shubhangi Saraf and Swastik Kopparty. Tolerant Linearity Testing and Locally Testable Codes
Accepted papers in Approx - Papers
- Ashkan Aazami, Joseph Cheriyan and Krishnam Raju Jampani. Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs
- Julia Chuzhoy and Paolo Codenotti. Resource Minimization Job Scheduling
- Ronald Koch, Britta Peis, Martin Skutella and Andreas Wiese. Real-Time Message Routing and Scheduling
- Katarzyna Paluch, Marcin Mucha and Aleksander Madry. A 7/9 Approximation Algorithm for the Maximum Traveling Salesman Problem
- Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev and Maxim Sviridenko. On Hardness of Pricing Items for Single-Minded Bidders
- Friedrich Eisenbrand and Thomas Rothvoss. New Hardness Results for Diophantine Approximation
- Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar and Danny Segev. Scheduling with Outliers
- Saurav Pandit, Sriram Pemmaraju and Kasturi Varadarajan. Approximation Algorithms for Domatic Partitions
- Brian Tagiku, Adam Meyerson and Douglas Carroll. Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
- Avner Magen and Mohammad Moharrami. Robust algorithms for Maximum Independent Set on Minor-free graphs based on the Sherali-Adams Hierarchy
- Jon Lee, Maxim Sviridenko and Jan Vondrak. Submodular Maximization Over Multiple Matroids via Generalized Exchange Properties
- Chandra Chekuri and Iftah Gamzu. Truthful Mechanisms via Greedy Iterative Packing
- Gaurav Kanade, Matt Gibson, Kasturi Varadarajan and Erik Krohn. An Approximation Scheme for Terrain Guarding
- Venkatesan Guruswami and Ali Kemal Sinop. Improved Inapproximability Results for Maximum k-Colorable Subgraph
- Chandra Chekuri, Alina Ene and Nitish Korula. Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
- Alexander Jaffe, James Lee and Mohammad Moharrami. On the optimality of gluing over scales
- Rolf Harren and Rob van Stee. Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
- Thomas Rothvoss and Laura Sanita. On the complexity of the asymmetric VPN problem
- Jose R. Correa, Martin Skutella and Jose Verschae. The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders
- Brian Tagiku and Adam Meyerson. Minimizing Average Shortest Path Distances via Shortcut Edge Addition
- Zeev Nutov. Approximating Node-Connectivity Augmentation Problems
- Guy Kortsraz and Zeev Nutov. Approximating some network design problems with node costs
- Konstantinos Georgiou, Avner Magen and Madhur Tulsiani. Optimal Sherali-Adams Gaps from Pairwise Independence
- Uriel Feige, Nicole Immorlica, Vahab Mirrokni and Hamid Nazerzadeh. Pass Approximation: A Framework for Analyzing and Designing Heuristics
- Ankit Aggarwal, Amit Deshpande and Ravi Kannan. Adaptive Sampling for k-means Clustering
|
PDF Format
Plain Text
