default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID16th RANDOM / 15th APPROX 2012: Cambridge, MA, USA
- Anupam Gupta, Klaus Jansen, José D. P. Rolim, Rocco A. Servedio
:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings. Lecture Notes in Computer Science 7408, Springer 2012, ISBN 978-3-642-32511-3
Contributed Talks of APPROX
- Per Austrin, Ryan O'Donnell, John Wright:
A New Point of NP-Hardness for 2-to-1 Label Cover. 1-12 - Per Austrin, Toniann Pitassi, Yu Wu:
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems. 13-24 - Pranjal Awasthi, Avrim Blum, Jamie Morgenstern, Or Sheffet:
Additive Approximation for Near-Perfect Phylogeny Construction. 25-36 - Pranjal Awasthi, Or Sheffet:
Improved Spectral-Norm Bounds for Clustering. 37-49 - Piotr Berman, Grigory Yaroslavtsev:
Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs. 50-60 - Petros Boufounos, Volkan Cevher, Anna C. Gilbert, Yi Li, Martin J. Strauss:
What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid. 61-72 - Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, Sanjeev Khanna:
Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply. 73-84 - Ho-Leung Chan, Tak Wah Lam, Rongbin Li:
Online Flow Time Scheduling in the Presence of Preemption Overhead. 85-97 - Chandra Chekuri, Alina Ene, Ali Vakilian:
Prize-Collecting Survivable Network Design in Node-Weighted Graphs. 98-109 - Joseph Cheriyan, Zachary Friggstad, Zhihan Gao:
Approximating Minimum-Cost Connected T-Joins. 110-121 - Michael Dinitz, Gordon T. Wilfong:
iBGP and Constrained Connectivity. 122-133 - Leah Epstein, Lukasz Jez, Jirí Sgall, Rob van Stee:
Online Scheduling of Jobs with Fixed Start Times on Related Machines. 134-145 - Cristina G. Fernandes, Luis A. A. Meira, Flávio Keidi Miyazawa, Lehilton L. C. Pedrosa:
A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems. 146-157 - Venkatesan Guruswami, Yuan Zhou:
Approximating Bounded Occurrence Ordering CSPs. 158-169 - Johan Håstad:
On the NP-Hardness of Max-Not-2. 170-181 - Ishay Haviv:
The Remote Set Problem on Lattices. 182-193 - Matthias Hellwig, Alexander Souza:
Approximation Algorithms for Generalized and Variable-Sized Bin Covering. 194-205 - Satoru Iwata, Prasad Tetali, Pushkar Tripathi:
Approximating Minimum Linear Ordering Problems. 206-217 - Samir Khuller, Barna Saha, Kanthi K. Sarpatwar:
New Approximation Results for Resource Replication Problems. 218-230 - Christian Konrad, Frédéric Magniez, Claire Mathieu:
Maximum Matching in Semi-streaming with Few Passes. 231-242 - Michael Lampis:
Improved Inapproximability for TSP. 243-253 - Konstantin Makarychev, Yury Makarychev:
Approximation Algorithm for Non-boolean MAX k-CSP. 254-265 - Yury Makarychev, Anastasios Sidiropoulos:
Planarizing an Unknown Surface. 266-275 - Dana Moshkovitz:
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. 276-287 - Rishi Saket, Maxim Sviridenko:
New and Improved Bounds for the Minimum Set Cover Problem. 288-300 - Ola Svensson:
Hardness of Vertex Deletion and Project Scheduling. 301-312 - Suguru Tamaki, Yuichi Yoshida:
Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues. 313-324 - Cenny Wenner:
Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four - (Extended Abstract). 325-337
Contributed Talks of RANDOM
- Anil Ada, Omar Fawzi, Hamed Hatami:
Spectral Norm of Symmetric Functions. 338-349 - Noga Alon, Shachar Lovett:
Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions. 350-361 - Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva:
Testing Permanent Oracles - Revisited. 362-373 - Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Limitations of Local Filters of Lipschitz and Monotone Functions. 374-386 - Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Testing Lipschitz Functions on Hypergrid Domains. 387-398 - Eli Ben-Sasson, Ariel Gabizon:
Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic. 399-410 - Petra Berenbrink, Artur Czumaj, Matthias Englert, Tom Friedetzky, Lars Nagel:
Multiple-Choice Balanced Allocation in (Almost) Parallel. 411-422 - Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan:
Optimal Hitting Sets for Combinatorial Shapes. 423-434 - Eric Blais, Daniel M. Kane:
Tight Bounds for Testing k-Linearity. 435-446 - Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan:
Pseudorandomness for Linear Length Branching Programs and Stack Machines. 447-458 - Mark Braverman, Omri Weinstein:
A Discrepancy Lower Bound for Information Complexity. 459-470 - Nader H. Bshouty:
On the Coin Weighing Problem with the Presence of Noise. 471-482 - Amit Chakrabarti, Ranganath Kondapally, Zhenghui Wang:
Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming. 483-494 - Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari:
An Explicit VC-Theorem for Low-Degree Polynomials. 495-504 - Varsha Dani, Cristopher Moore, Anna Olson:
Tight Bounds on the Threshold for Permuted k-Colorability. 505-516 - Anirban Dasgupta, Ravi Kumar, D. Sivakumar:
Sparse and Lopsided Set Disjointness via Information Theory. 517-528 - Adrian Dumitrescu, Minghui Jiang:
Maximal Empty Boxes Amidst Random Points. 529-540 - Alan M. Frieze, Charalampos E. Tsourakakis:
Rainbow Connectivity of Sparse Random Graphs. 541-552 - Ariel Gabizon, Ronen Shaltiel:
Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors. 553-564 - Oded Goldreich, Igor Shinkar:
Two-Sided Error Proximity Oblivious Testing - (Extended Abstract). 565-578 - Prateek Jain, Abhradeep Thakurta:
Mirror Descent Based Database Privacy. 579-590 - Ragesh Jaiswal, Nitin Garg:
Analysis of k-Means++ for Separable Data. 591-602 - Kashyap Babu Rao Kolipaka, Mario Szegedy, Yixin Xu:
A Sharper Local Lemma with Improved Applications. 603-614 - Tsz Chiu Kwok, Lap Chi Lau:
Finding Small Sparse Cuts by Random Walk. 615-626 - Jelani Nelson, Huy L. Nguyên, David P. Woodruff:
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. 627-638 - Noga Ron-Zewi, Madhu Sudan:
A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes. 639-650 - Michael Viderman:
A Combination of Testability and Decodability by Tensor Products. 651-662 - Emanuele Viola:
Extractors for Turing-Machine Sources. 663-671
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-25 00:35 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
