15. RANDOM / 14. APPROX 2011: Princeton, NJ, USA

Contributed Talks of APPROX

• Sanjeev Arora, Rong Ge:
  New Tools for Graph Coloring. 1-12
  
• Per Austrin, Mark Braverman, Eden Chlamtac:
  Inapproximability of NP-Complete Variants of Nash Equilibrium. 13-25
  
• Khanh Do Ba, Piotr Indyk:
  Sparse Recovery with Partial Support Knowledge. 26-37
  
• Nikhil Bansal, Ravishankar Krishnaswamy, Barna Saha:
  On Capacitated Set Cover Problems. 38-49
  
• Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman:
  Bandwidth and Low Dimensional Embedding. 50-61
  
• Piotr Berman, Erik D. Demaine, Morteza Zadimoghaddam:
  O(1)-Approximations for Maximum Movement Problems. 62-74
  
• Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
  Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs. 75-86
  
• Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
  Social Welfare in One-Sided Matching Markets without Money. 87-98
  
• Tim Carnes, David B. Shmoys:
  Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem. 99-110
  
• Venkatesan T. Chakaravarthy, Amit Kumar, Vinayaka Pandit, Sambuddha Roy, Yogish Sabharwal:
  Scheduling Resources for Throughput Maximization. 111-122
  
• Parinya Chalermsook:
  Coloring and Maximum Independent Set of Rectangles. 123-134
  
• Maurice Cheung, David B. Shmoys:
  A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems. 135-146
  
• Nachshon Cohen, Zeev Nutov:
  A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius. 147-157
  
• Michael S. Crouch, Andrew McGregor:
  Periodicity and Cyclic Shifts via Linear Sketches. 158-170
  
• Feodor F. Dragan, Ekkehard Köhler:
  An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs. 171-183
  
• Chandan K. Dubey, Thomas Holenstein:
  Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle. 184-193
  
• Adrian Dumitrescu, Minghui Jiang, János Pach:
  Opaque Sets. 194-205
  
• Sándor P. Fekete, Tom Kamphans, Alexander Kröller, Joseph S. B. Mitchell, Christiane Schmidt:
  Exploring and Triangulating a Region by a Swarm of Robots. 206-217
  
• Moran Feldman, Joseph Naor, Roy Schwartz:
  Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract). 218-229
  
• Inge Li Gørtz, Viswanath Nagarajan:
  Locating Depots for Capacitated Vehicle Routing. 230-241
  
• Johan Håstad:
  Satisfying Degree-d Equations over GF[2] n. 242-253
  
• Zhiyi Huang, Lei Wang, Yuan Zhou:
  Black-Box Reductions in Mechanism Design. 254-265
  
• Michael Kapralov, Rina Panigrahy:
  Multiplicative Approximations of Random Walk Transition Probabilities. 266-276
  
• Marek Karpinski, Warren Schudy:
  Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems. 277-288
  
• Rohit Khandekar, Guy Kortsarz, Zeev Nutov:
  Network-Design with Degree Constraints. 289-301
  
• M. Reza Khani, Mohammad R. Salavatipour:
  Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems. 302-314
  
• Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala:
  Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions. 315-326
  
• Sushant Sachdeva, Rishi Saket:
  Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs. 327-338
  
• Sagi Snir, Raphael Yuster:
  A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs. 339-350
  

Contributed Talks of RANDOM

• Mohammed Abdullah, Colin Cooper, Moez Draief:
  Viral Processes by Random Walks on Random Regular Graphs. 351-364
  
• Andris Ambainis, Andrew M. Childs, Yi-Kai Liu:
  Quantum Property Testing for Bounded-Degree Graphs. 365-376
  
• Sergei Artemenko, Ronen Shaltiel:
  Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification. 377-388
  
• Lidor Avigad, Oded Goldreich:
  Testing Graph Blow-Up. 389-399
  
• Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
  On Sums of Locally Testable Affine Invariant Properties. 400-411
  
• Eli Ben-Sasson, Madhu Sudan:
  Limits on the Rate of Locally Testable Affine-Invariant Codes. 412-423
  
• Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel:
  The Computational Complexity of Estimating MCMC Convergence Time. 424-435
  
• Joshua Brody, David P. Woodruff:
  Streaming Algorithms with One-Sided Estimation. 436-447
  
• Amit Chakrabarti, Ranganath Kondapally:
  Everywhere-Tight Information Cost Tradeoffs for Augmented Index. 448-459
  
• Dana Dachman-Soled, Rocco A. Servedio:
  A Canonical Form for Testing Boolean Function Properties. 460-471
  
• Varsha Dani, Cristopher Moore:
  Independent Sets in Random Graphs from the Weighted Second Moment Method. 472-482
  
• Anindya De, Thomas Watson:
  Extractors and Lower Bounds for Locally Samplable Sources. 483-494
  
• Domingos Dellamonica Jr., Subrahmanyam Kalyanasundaram, Daniel M. Martin, Vojtech Rödl, Asaf Shapira:
  A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma. 495-506
  
• Irit Dinur, Tali Kaufman:
  Dense Locally Testable Codes Cannot Have Constant Rate and Distance. 507-518
  
• Andrew Drucker:
  Efficient Probabilistically Checkable Debates. 519-529
  
• Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak:
  An Efficient Partitioning Oracle for Bounded-Treewidth Graphs. 530-541
  
• Eldar Fischer, Eyal Rozenberg:
  Inflatable Graph Properties and Natural Property Tests. 542-554
  
• Tobias Friedrich, Lionel Levine:
  Fast Simulation of Large-Scale Growth Models. 555-566
  
• Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, Linji Yang:
  Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model. 567-578
  
• Oded Goldreich, Tali Kaufman:
  Proximity Oblivious Testing and the Role of Invariances. 579-592
  
• Venkatesan Guruswami, Carol Wang:
  Optimal Rate List Decoding via Derivative Codes. 593-604
  
• Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wootters:
  Public Key Locally Decodable Codes with Short Keys. 605-615
  
• Zhiyi Huang, Sampath Kannan:
  On Sampling from Multivariate Distributions. 616-627
  
• Daniel M. Kane, Raghu Meka, Jelani Nelson:
  Almost Optimal Explicit Johnson-Lindenstrauss Families. 628-639
  
• Shachar Lovett, Srikanth Srinivasan:
  Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 - o(1) Symmetric Gates. 640-651
  
• Sarah Miracle, Dana Randall, Amanda Pascoe Streib:
  Clustering in Interfering Binary Mixtures. 652-663
  
• Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein:
  Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity. 664-675
  
• Dana Ron, Gilad Tsur:
  On Approximating the Number of Relevant Variables in a Function. 676-687
  
• Thomas Watson:
  Query Complexity in Errorless Hardness Amplification. 688-699
  

Last update Sat May 18 00:03:50 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page