| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Yishay Mansour, Shai Vardi |
A Local Computation Approximation Scheme to Maximum Matching.  |
APPROX-RANDOM  |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Sixia Chen, Cristopher Moore, Alexander Russell |
Small-Bias Sets for Nonabelian Groups - Derandomizations of the Alon-Roichman Theorem. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Roee David, Uriel Feige |
Connectivity of Random High Dimensional Geometric Graphs. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Pinyan Lu, Yitong Yin |
Improved FPTAS for Multi-spin Systems. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | MohammadTaghi Hajiaghayi, Rohit Khandekar, M. Reza Khani, Guy Kortsarz |
Approximation Algorithms for Movement Repairmen. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Elad Haramaty, Noga Ron-Zewi, Madhu Sudan 0001 |
Absolutely Sound Testing of Lifted Codes. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Pierre Fraigniaud, Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz, Adi Rosén |
Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir Braverman, Rafail Ostrovsky |
Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Forbes 0001, Amir Shpilka |
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Ishai, Amit Sahai, Michael Viderman, Mor Weiss |
Zero Knowledge LTCs and Their Applications. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthew Coudron, Thomas Vidick, Henry Yuen |
Robust Randomness Amplifiers: Upper and Lower Bounds. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Juan Carlos Vera 0001, Eric Vigoda, Linji Yang |
Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Edith Cohen, Haim Kaplan, Yishay Mansour |
Scheduling Subset Tests: One-Time, Continuous, and How They Relate. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Zachary Friggstad |
Multiple Traveling Salesmen in Asymmetric Metrics. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Srivatsan Narayanan |
Combinatorial Limitations of Average-Radius List Decoding. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Yi Li 0002, David P. Woodruff |
A Tight Lower Bound for High Frequency Moment Estimation with Small Error. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Meyerson, Alan Roytman, Brian Tagiku |
Online Multidimensional Load Balancing. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Sangxia Huang |
Improved Hardness of Approximating Chromatic Number. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, José D. P. Rolim (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Kyle Fox, Sungjin Im, Janardhan Kulkarni, Benjamin Moseley |
Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Saeed Alaei, MohammadTaghi Hajiaghayi, Vahid Liaghat |
The Online Stochastic Generalized Assignment Problem. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir Braverman, Rafail Ostrovsky |
Approximating Large Frequency Moments with Pick-and-Drop Sampling. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Emmanuel Abbe, Andrea Montanari |
Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Deeparnab Chakrabarty, C. Seshadhri 0001 |
An Optimal Lower Bound for Monotonicity Testing over Hypergrids. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Avrim Blum, Aaron Roth 0001 |
Fast Private Data Release Algorithms for Sparse Queries. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Rajsekar Manokaran, Cenny Wenner |
On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeyu Guo 0001 |
Randomness-Efficient Curve Samplers. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrea Campagna, Alan Guo, Ronitt Rubinfeld |
Local Reconstructors and Tolerant Testers for Connectivity and Diameter. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Edith Cohen, Haim Kaplan |
What You Can Do with Coordinated Samples. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Sándor P. Fekete, Hella-Franziska Hoffmann |
Online Square-into-Square Packing. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrew McGregor 0001, Daniel M. Stubbs |
Sketching Earth-Mover Distance on Graph Metrics. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Shayan Oveis Gharan, Luca Trevisan |
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Varsha Dani, Josep Díaz, Thomas P. Hayes, Cristopher Moore |
The Power of Choice for Random Satisfiability. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Adrian Dumitrescu, Csaba D. Tóth |
On the Total Perimeter of Homothetic Convex Bodies in a Convex Container. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Joseph Cheriyan, Zachary Friggstad, Zhihan Gao 0002 |
Approximating Minimum-Cost Connected T-Joins. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari |
An Explicit VC-Theorem for Low-Degree Polynomials. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandra Chekuri, Alina Ene, Ali Vakilian |
Prize-Collecting Survivable Network Design in Node-Weighted Graphs. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Dinitz, Gordon T. Wilfong |
iBGP and Constrained Connectivity. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Petra Berenbrink, Artur Czumaj, Matthias Englert, Tom Friedetzky, Lars Nagel 0001 |
Multiple-Choice Balanced Allocation in (Almost) Parallel. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ishay Haviv |
The Remote Set Problem on Lattices. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Prateek Jain 0002, Abhradeep Thakurta |
Mirror Descent Based Database Privacy. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Pranjal Awasthi, Madhav Jha, Marco Molinaro 0001, Sofya Raskhodnikova |
Testing Lipschitz Functions on Hypergrid Domains. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Dana Moshkovitz |
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, Sanjeev Khanna |
Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan 0001 |
Optimal Hitting Sets for Combinatorial Shapes. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Kashyap Babu Rao Kolipaka, Mario Szegedy, Yixin Xu |
A Sharper Local Lemma with Improved Applications. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Yury Makarychev, Anastasios Sidiropoulos |
Planarizing an Unknown Surface. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Ryan O'Donnell, John Wright 0004 |
A New Point of NP-Hardness for 2-to-1 Label Cover. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Arora, Arnab Bhattacharyya 0001, Rajsekar Manokaran, Sushant Sachdeva |
Testing Permanent Oracles - Revisited. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Konstantin Makarychev, Yury Makarychev |
Approximation Algorithm for Non-boolean MAX k-CSP. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Yuan Zhou 0007 |
Approximating Bounded Occurrence Ordering CSPs. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Leah Epstein, Lukasz Jez, Jirí Sgall, Rob van Stee |
Online Scheduling of Jobs with Fixed Start Times on Related Machines. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Konrad 0001, Frédéric Magniez, Claire Mathieu |
Maximum Matching in Semi-streaming with Few Passes. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Ranganath Kondapally, Zhenghui Wang |
Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Anirban Dasgupta 0001, Ravi Kumar 0001, D. Sivakumar 0001 |
Sparse and Lopsided Set Disjointness via Information Theory. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Adrian Dumitrescu, Minghui Jiang 0001 |
Maximal Empty Boxes Amidst Random Points. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Suguru Tamaki, Yuichi Yoshida |
Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Shachar Lovett |
Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jelani Nelson, Huy L. Nguyên, David P. Woodruff |
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Grigory Yaroslavtsev |
Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Ron-Zewi, Madhu Sudan 0001 |
A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ho-Leung Chan, Tak Wah Lam, Rongbin Li |
Online Flow Time Scheduling in the Presence of Preemption Overhead. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ola Svensson |
Hardness of Vertex Deletion and Project Scheduling. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Anil Ada, Omar Fawzi, Hamed Hatami |
Spectral Norm of Symmetric Functions. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Satoru Iwata 0001, Prasad Tetali, Pushkar Tripathi |
Approximating Minimum Linear Ordering Problems. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthias Hellwig, Alexander Souza |
Approximation Algorithms for Generalized and Variable-Sized Bin Covering. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Pranjal Awasthi, Avrim Blum, Jamie Morgenstern, Or Sheffet |
Additive Approximation for Near-Perfect Phylogeny Construction. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Alan M. Frieze, Charalampos E. Tsourakakis |
Rainbow Connectivity of Sparse Random Graphs. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich 0001, Igor Shinkar |
Two-Sided Error Proximity Oblivious Testing - (Extended Abstract). |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
On the NP-Hardness of Max-Not-2. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Petros Boufounos, Volkan Cevher, Anna C. Gilbert, Yi Li 0002, Martin J. Strauss |
What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Pranjal Awasthi, Or Sheffet |
Improved Spectral-Norm Bounds for Clustering. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Cenny Wenner |
Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four - (Extended Abstract). |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan |
Pseudorandomness for Linear Length Branching Programs and Stack Machines. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Varsha Dani, Cristopher Moore, Anna Olson |
Tight Bounds on the Threshold for Permuted k-Colorability. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ragesh Jaiswal, Nitin Garg |
Analysis of k-Means++ for Separable Data. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Pranjal Awasthi, Madhav Jha, Marco Molinaro 0001, Sofya Raskhodnikova |
Limitations of Local Filters of Lipschitz and Monotone Functions. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Viderman |
A Combination of Testability and Decodability by Tensor Products. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Rishi Saket, Maxim Sviridenko |
New and Improved Bounds for the Minimum Set Cover Problem. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola |
Extractors for Turing-Machine Sources. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Toniann Pitassi, Yu Wu |
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta 0001, Klaus Jansen, José D. P. Rolim, Rocco A. Servedio (eds.) |
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 |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Blais, Daniel M. Kane |
Tight Bounds for Testing k-Linearity. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Samir Khuller, Barna Saha, Kanthi K. Sarpatwar |
New Approximation Results for Resource Replication Problems. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Tsz Chiu Kwok, Lap Chi Lau |
Finding Small Sparse Cuts by Random Walk. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Ariel Gabizon |
Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Lampis |
Improved Inapproximability for TSP. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Omri Weinstein |
A Discrepancy Lower Bound for Information Complexity. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Nader H. Bshouty |
On the Coin Weighing Problem with the Presence of Noise. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ariel Gabizon, Ronen Shaltiel |
Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors. |
APPROX-RANDOM |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Moran Feldman, Joseph Naor, Roy Schwartz 0002 |
Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract). |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | M. Reza Khani, Mohammad R. Salavatipour |
Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna |
Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Klaus Jansen, R. Ravi 0001, José D. P. Rolim (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Ranganath Kondapally |
Everywhere-Tight Information Cost Tradeoffs for Augmented Index. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Sagi Snir, Raphael Yuster |
A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Warren Schudy |
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Varsha Dani, Cristopher Moore |
Independent Sets in Random Graphs from the Weighted Second Moment Method. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandan K. Dubey, Thomas Holenstein |
Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license