14. RANDOM / 13. APPROX 2010: Barcelona, Spain

Contributed Talks of APPROX

• Hyung-Chan An, Robert D. Kleinberg, David B. Shmoys:
  Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem. 1-11
  
• Per Austrin:
  Improved Inapproximability for Submodular Maximization. 12-24
  
• MohammadHossein Bateni, Julia Chuzhoy:
  Approximation Algorithms for the Directed k-Tour and k-Stroll Problems. 25-38
  
• MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Morteza Zadimoghaddam:
  Submodular Secretary Problem and Extensions. 39-52
  
• Piotr Berman, Sofya Raskhodnikova:
  Approximation Algorithms for Min-Max Generalization Problems. 53-66
  
• Gruia Calinescu:
  Min-Power Strong Connectivity. 67-80
  
• Prasad Chebolu, Leslie Ann Goldberg, Russell A. Martin:
  The Complexity of Approximately Counting Stable Matchings. 81-94
  
• Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès:
  Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. 95-109
  
• Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson:
  Approximating Linear Threshold Predicates. 110-123
  
• Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra:
  Approximating Sparsest Cut in Graphs of Bounded Treewidth. 124-137
  
• Irit Dinur, Igor Shinkar:
  On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors. 138-151
  
• Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar:
  Vertex Sparsifiers: New Results from Old Techniques. 152-165
  
• Thomas Erlebach, Erik Jan van Leeuwen:
  PTAS for Weighted Set Cover on Unit Squares. 166-177
  
• Igor Gorodezky, Robert D. Kleinberg, David B. Shmoys, Gwen Spencer:
  Improved Lower Bounds for the Universal and a priori TSP. 178-191
  
• Lee-Ad Gottlieb, Robert Krauthgamer:
  Proximity Algorithms for Nearly-Doubling Spaces. 192-204
  
• Lee-Ad Gottlieb, Tyler Neylon:
  Matrix Sparsification and the Sparse Null Space Problem. 205-218
  
• MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Julián Mestre:
  The Checkpoint Problem. 219-231
  
• Ishay Haviv, Oded Regev:
  The Euclidean Distortion of Flat Tori. 232-245
  
• Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, Anastasios Zouzias:
  Online Embeddings. 246-259
  
• Frank Kammer, Torsten Tholey, Heiko Voepel:
  Approximation Algorithms for Intersection Graphs. 260-273
  
• Ken-ichi Kawarabayashi, Yusuke Kobayashi:
  An O(logn)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs. 274-286
  
• Ken-ichi Kawarabayashi, Yusuke Kobayashi:
  Improved Algorithm for the Half-Disjoint Paths Problem. 287-297
  
• Subhash Khot, Preyas Popat, Rishi Saket:
  Approximate Lasserre Integrality Gap for Unique Games. 298-311
  
• Spyros C. Kontogiannis, Paul G. Spirakis:
  Exploiting Concavity in Bimatrix Games: New Polynomially Tractable Subclasses. 312-325
  
• Guyslain Naves, Nicolas Sonnerat, Adrian Vetta:
  Maximum Flows on Disjoint Paths. 326-337
  
• Evdokia Nikolova:
  Approximation Algorithms for Reliable Stochastic Combinatorial Optimization. 338-351
  
• Kirk Pruhs, Clifford Stein:
  How to Schedule When You Have to Buy Your Energy. 352-365
  
• Mohit Singh, Kunal Talwar:
  Improving Integrality Gaps via Chvátal-Gomory Rounding. 366-379
  

Contributed Talks of RANDOM

• Eric Allender, Vikraman Arvind, Fengming Wang:
  Uniform Derandomization from Pathetic Lower Bounds. 380-393
  
• Noga Alon, Eric Blais:
  Testing Boolean Function Isomorphism. 394-405
  
• Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh:
  Better Size Estimation for Sparse Matrix Products. 406-419
  
• Eli Ben-Sasson, Michael Viderman:
  Low Rate Is Insufficient for Local Testability. 420-433
  
• Nayantara Bhatnagar, Allan Sly, Prasad Tetali:
  Reconstruction Threshold for the Hardcore Model. 434-447
  
• Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
  Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. 448-461
  
• Jop Briët, Sourav Chakraborty, David García-Soriano, Arie Matsliah:
  Monotonicity Testing and Shortest-Path Routing on the Cube. 462-475
  
• Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf:
  Better Gap-Hamming Lower Bounds via Better Round Elimination. 476-489
  
• Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe:
  Propagation Connectivity of Random Hypergraphs. 490-503
  
• Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani:
  Improved Pseudorandom Generators for Depth 2 Circuits. 504-517
  
• Irit Dinur, Elazar Goldenberg:
  The Structure of Winning Strategies in Parallel Repetition Games. 518-530
  
• Elya Dolev, Dana Ron:
  Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries. 531-544
  
• Funda Ergün, Hossein Jowhari, Mert Saglam:
  Periodicity in Streams. 545-559
  
• Nikolaos Fountoulakis, Konstantinos Panagiotou:
  Rumor Spreading on Random Regular Graphs and Expanders. 560-573
  
• Oded Goldreich:
  On Testing Computability by Small Width OBDDs. 574-587
  
• Parikshit Gopalan, Rocco A. Servedio:
  Learning and Lower Bounds for AC⁰ with Threshold Gates. 588-601
  
• Thomas P. Hayes, Alistair Sinclair:
  Liftings of Tree-Structured Markov Chains - (Extended Abstract). 602-616
  
• Russell Impagliazzo, Valentine Kabanets:
  Constructive Proofs of Concentration Bounds. 617-631
  
• Piotr Indyk, Stanislaw Szarek:
  Almost-Euclidean Subspaces of l₁^N\ell_1^N via Tensor Products: A Simple Approach to Randomness Reduction. 632-641
  
• Yuichi Yoshida, Hiro Ito:
  Testing Outerplanarity of Bounded Degree Graphs. 642-655
  
• Roy Kasher, Julia Kempe:
  Two-Source Extractors Secure against Quantum Adversaries. 656-669
  
• Tali Kaufman, Michael Viderman:
  Locally Testable vs. Locally Decodable Codes. 670-682
  
• Aaron Roth:
  Differential Privacy and the Fat-Shattering Dimension of Linear Queries. 683-695
  
• Atri Rudra, Steve Uurtamo:
  Two Theorems on List Decoding - (Extended Abstract). 696-709
  
• Alistair Sinclair, Dan Vilenchik:
  Delaying Satisfiability for Random 2SAT. 710-723
  
• David Steurer:
  Improved Rounding for Parallel Repeated Unique Games. 724-737
  
• Suguru Tamaki, Yuichi Yoshida:
  A Query Efficient Non-adaptive Long Code Test with Perfect Completeness. 738-751
  
• Thomas Watson:
  Relativized Worlds without Worst-Case to Average-Case Reductions for NP. 752-765
  
• David P. Woodruff:
  A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. 766-779
  

Last update Wed May 22 22:51:24 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page