|
Accepted papers in Random - Papers
- Arie Matsliah, Jop Briet, Sourav Chakraborty and David García-Soriano. Monotonicity Testing and Shortest-Path Routing on the Cube
- Thomas Watson. Relativized Worlds Without Worst-Case to Average-Case Reductions for NP
- Eli Ben-Sasson and Michael Viderman. Low Rate Is Insufficient for Local Testability
- Suguru Tamaki and Yuichi Yoshida. A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness
- Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick and Ronald de Wolf. Better Gap-Hamming Lower Bounds via Better Round Elimination
- Oded Goldreich. On Testing Computability by Small Width OBDDs
- Tali Kaufman and Michael Viderman. Locally Testable vs. Locally Decodable Codes
- Yuichi Yoshida and Hiro Ito. Testing Outerplanarity of Bounded Degree Graphs
- David Woodruff. A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
- Dana Ron and Elya dolev. Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries
- Aaron Roth. Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Parikshit Gopalan and Rocco Servedio. Learning and Lower Bounds for AC^0 with Threshold Gates
- Elazar Goldenberg and Irit Dinur. The Structure of Winning Strategies in Parallel Repetition Games
- Eric Allender, V Arvind and Fengming Wang. Uniform Derandomization from Pathetic Lower Bounds
- Rasmus R. Amossen, Andrea Campagna and Rasmus Pagh. Better size estimation for sparse matrix products
- Amin Coja-Oghlan, Mikael Onsjö and Osamu Watanabe. Propagation Connectivity of Random Hypergraphs
- Nikolaos Fountoulakis and Konstantinos Panagiotou. Rumor spreading on random regular graphs and expanders
- Funda Ergun, Hossein Jowhari and Mert Saglam. Periodicity in Streams
- Atri Rudra and Steve Uurtamo. Two Theorems on List Decoding
- Piotr Indyk and Stanislaw Szarek. Almost-Euclidean subspaces of ell_1^N via tensor products: a simple approach to randomness reduction
- Roy Kasher and Julia Kempe. Two-source Extractors Secure Against Quantum Adversaries
- Noga Alon and Eric Blais. Testing boolean function isomorphism
- Nayantara Bhatnagar, Allan Sly and Prasad Tetali. Reconstruction threshold for the hardcore model
- Russell Impagliazzo and Valentine Kabanets. Constructive Proofs of Concentration Bounds
- Anindya De, Omid Etesami, Luca Trevisan and Madhur Tulsiani. Improved Pseudorandom Generators for Depth 2 Circuits
- Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova and David Woodruff. Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
- Alistair Sinclair and Dan Vilenchik. Delaying satisfiability for random 2SAT
- Thomas Hayes and Alistair Sinclair. Liftings of Tree-Structured Markov Chains
- David Steurer. Improved Rounding for Parallel Repeated Unique Games
Accepted papers in Approx - Papers
- Preyas Popat, Subhash Khot and Rishi Saket. Approximate Lasserre Integrality Gap for Unique Games
- Ishay Haviv and Oded Regev. The Euclidean Distortion of Flat Tori
- Irit Dinur and Igor Shinkar. On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors
- Ken-ichi Kawarabayashi and Yusuke Kobayashi. An O(log n)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs
- Frank Kammer and Torsten Tholey. Approximation Algorithms for Intersection Graphs
- Prasad Chebolu , Leslie Ann Goldberg and Russell Martin. The Complexity of Approximately Counting Stable Matchings
- Spyros Kontogiannis and Paul Spirakis. Exploiting Concavity in Bimatrix Games: New polynomially tractable subclasses
- MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz and Julian Mestre. The Checkpoint Problem
- Kirk Pruhs and Clifford Stein. How To Schedule When You Have To Buy Your Energy
- Mahdi Cheraghchi, Johan Hastad, Marcus Isaksson and Ola Svensson. Approximating Linear Threshold Predicates
- Mohammad Hossein Bateni and Julia Chuzhoy . Approximation Algorithms for the Directed k-Stroll and k-Tour Problems
- Mohit Singh and Kunal Talwar. Improving Integrality Gaps via \chvatal-Gomory Rounding
- Per Austrin. Improved Inapproximability For Submodular Maximization
- Piotr Berman and Sofya Raskhodnikova. Approximation Algorithms for Min-Max Generalization Problems
- Igor Gorodezky, Robert Kleinberg, David Shmoys and Gwen Spencer. Improved lower bounds for the universal and a priori TSP
- MohammadHossein Bateni, MohammadTaghi Hajiaghayi and Morteza Zadimoghaddam . Submodular Secretary Problem and Extensions
- Eden Chlamtac , Robert Krauthgamer and Prasad Raghavendra. Approximating Sparsest Cut in Graphs of Bounded Treewidth
- Ken-ichi Kawarabayashi and Yusuke Kobayashi. Improved Algorithm for the Half-Disjoint Paths Problem
- Lee-Ad Gottlieb and Tyler Neylon. Matrix sparsification and the sparse null space problem
- Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Raecke, Inbal Talgam and Kunal Talwar. Vertex Sparsifiers: New Results from Old Techniques
- Guyslain Naves, Nicolas Sonnerat and Adrian Vetta. Maximum Flows on Disjoint Paths
- Piotr Indyk , Avner Magen, Anastasios Sidiropoulos and Anastasios Zouzias. On-line Embeddings
- Hyung-Chan An, Robert D. Kleinberg and David B. Shmoys. Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
- Victor Chepoi, Feodor Dragan, Ilan Newman, Yuri Rabinovich and Yann Vaxes. Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
- Thomas Erlebach and Erik Jan van Leeuwen. PTAS for Weighted Set Cover on Unit Squares
- Evdokia Nikolova. Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
- Lee-Ad Gottlieb and Robi Krauthgamer. Proximity algorithms for nearly-doubling spaces
- Gruia Calinescu. Min-Power Strong Connectivity
|
PDF Format
Plain Text
