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 updated on Mon May 20 01:43:58 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page