| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Noga Alon, Eric Blais |
Testing Boolean Function Isomorphism.  |
APPROX-RANDOM  |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Roth 0001 |
Differential Privacy and the Fat-Shattering Dimension of Linear Queries. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas Erlebach, Erik Jan van Leeuwen |
PTAS for Weighted Set Cover on Unit Squares. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Funda Ergün, Hossein Jowhari, Mert Saglam |
Periodicity in Streams. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthias Englert, Anupam Gupta 0001, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar |
Vertex Sparsifiers: New Results from Old Techniques. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Maria J. Serna, Ronen Shaltiel, Klaus Jansen, José D. P. Rolim (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra |
Approximating Sparsest Cut in Graphs of Bounded Treewidth. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Kirk Pruhs, Clifford Stein 0001 |
How to Schedule When You Have to Buy Your Energy. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Rina Panigrahy, Sergey Yekhanin |
Deterministic Approximation Algorithms for the Nearest Codeword Problem. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Kortsarz, Zeev Nutov |
Approximating Some Network Design Problems with Node Costs. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
Node costs, Multicommodity Buy at Bulk, Covering tree, Approximation algorithm, Network design, Hardness of approximation |
| 1 | Saurav Pandit, Sriram V. Pemmaraju, Kasturi R. Varadarajan |
Approximation Algorithms for Domatic Partitions of Unit Disk Graphs. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Karthekeyan Chandrasekaran, Amit Deshpande 0001, Santosh S. Vempala |
Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankit Aggarwal, Amit Deshpande 0001, Ravi Kannan |
Adaptive Sampling for k-Means Clustering. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Shpilka, Ilya Volkovich |
Improved Polynomial Identity Testing for Read-Once Formulas. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Klim Efremenko, Omer Reingold |
How Well Do Random Walks Parallelize?. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
Markov Chains, Random Walks |
| 1 | Victor Chen |
A Hypergraph Dictatorship Test with Perfect Completeness. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
Gowers norm, Property testing, Fourier analysis, PCP |
| 1 | Swastik Kopparty, Shubhangi Saraf |
Tolerant Linearity Testing and Locally Testable Codes. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh |
PASS Approximation. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Chuzhoy, Paolo Codenotti |
Erratum: Resource Minimization Job Scheduling. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich 0001, Dana Ron |
Algorithmic Aspects of Property Testing in the Dense Graphs Model. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | José R. Correa, Martin Skutella, José Verschae |
The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Dana Ron, Gilad Tsur |
Testing Computability by Width Two OBDDs. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandra Chekuri, Iftah Gamzu |
Truthful Mechanisms via Greedy Iterative Packing. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio |
Testing ±1-weight halfspace. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Alan M. Frieze, Páll Melsted, Michael Mitzenmacher |
An Analysis of Random-Walk Cuckoo Hashing. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
Random Walk Algorithm, Cuckoo Hashing |
| 1 | Venkatesan Guruswami, Ali Kemal Sinop |
Improved Inapproximability Results for Maximum k-Colorable Subgraph. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | S. Charles Brubaker, Santosh S. Vempala |
Random Tensors and Planted Cliques. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Terence Tao, Van H. Vu |
Smooth Analysis of the Condition Number and the Least Singular Value. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Prasad Chebolu, Alan M. Frieze, Páll Melsted, Gregory B. Sorkin |
Average-Case Analyses of Vickrey Costs. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
VCG auction, Random Assignment Problem, shortest path, minimum spanning tree, random graph, Average-case analysis, MST |
| 1 | Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani |
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich 0001, Michael Krivelevich, Ilan Newman, Eyal Rozenberg |
Hierarchy Theorems for Property Testing. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
Monotone Graph Properties, Graph Blow-up, One-Sided vs Two-Sided Error, Adaptivity vs Non-adaptivity, Property Testing, Graph Properties |
| 1 | Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko |
On Hardness of Pricing Items for Single-Minded Bidders. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Shachar Lovett, Omer Reingold, Luca Trevisan, Salil P. Vadhan |
Pseudorandom Bit Generators That Fool Modular Sums. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Matt Gibson 0001, Gaurav Kanade, Erik Krohn, Kasturi R. Varadarajan |
An Approximation Scheme for Terrain Guarding. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Klaus Jansen, Joseph Naor, José D. P. Rolim (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Raghu Meka, David Zuckerman |
Small-Bias Spaces for Group Products. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Jon Lee 0001, Maxim Sviridenko, Jan Vondrák |
Submodular Maximization over Multiple Matroids via Generalized Exchange Properties. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam R. Klivans, Philip M. Long, Alex K. Tang |
Baum's Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronald Koch, Britta Peis, Martin Skutella, Andreas Wiese |
Real-Time Message Routing and Scheduling. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Anup Rao 0001, Ran Raz, Ricky Rosen, Ronen Shaltiel |
Strong Parallel Repetition Theorem for Free Projection Games. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Avner Magen, Mohammad Moharrami |
Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Rolf Harren, Rob van Stee |
Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
two-dimensional bin packing, absolute worst-case ratio, approximation algorithm, strip packing, rectangle packing |
| 1 | Lorenz Minder, Dan Vilenchik |
Small Clique Detection and Approximate Nash Equilibria. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Aram W. Harrow, Richard Andrew Low |
Efficient Quantum Tensor Product Expanders and k-Designs. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Konstantinos Georgiou, Avner Magen, Madhur Tulsiani |
Optimal Sherali-Adams Gaps from Pairwise Independence. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Michael Viderman |
Composition of Semi-LTCs by Two-Wise Tensor Products. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Katarzyna E. Paluch 0001, Marcin Mucha, Aleksander Madry |
A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Friedrich Eisenbrand, Thomas Rothvoß |
New Hardness Results for Diophantine Approximation. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Elena Grigorescu, Tali Kaufman, Madhu Sudan 0001 |
Succinct Representation of Codes with Applications to Testing. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
affine/cyclic invariance, single orbit, Locally testable codes |
| 1 | Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel |
Pseudorandom Generators and Typically-Correct Derandomization. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Nutov |
Approximating Node-Connectivity Augmentation Problems. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | T. S. Jayram |
Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta 0001, Ravishankar Krishnaswamy, Amit Kumar 0001, Danny Segev |
Scheduling with Outliers. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandra Chekuri, Alina Ene, Nitish Korula |
Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Chuzhoy, Paolo Codenotti |
Resource Minimization Job Scheduling. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Youming Qiao |
On the Security of Goldreich's One-Way Function. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Douglas E. Carroll, Adam Meyerson, Brian Tagiku |
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Brendan Lucier, Michael Molloy 0001, Yuval Peres |
The Glauber Dynamics for Colourings of Bounded Degree Trees. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas Rothvoß, Laura Sanità |
On the Complexity of the Asymmetric VPN Problem. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Luca Trevisan |
Extractors Using Hardness Amplification. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
Extractors, Direct product theorems, Hardness amplification |
| 1 | Adam Meyerson, Brian Tagiku |
Minimizing Average Shortest Path Distances via Shortcut Edge Addition. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander Jaffe, James R. Lee, Mohammad Moharrami |
On the Optimality of Gluing over Scales. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Ido Ben-Eliezer, Rani Hod, Shachar Lovett |
Random Low Degree Polynomials are Hard to Approximate. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Adrian Dumitrescu, Minghui Jiang 0001 |
Sweeping Points. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson |
Approximating Single Machine Scheduling with Scenarios. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Nicla Bernasconi, Konstantinos Panagiotou, Angelika Steger |
On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Anup Rao 0001 |
A 2-Source Almost-Extractor for Linear Entropy. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Bresler, Elchanan Mossel, Allan Sly |
Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Arash Asadpour, Uriel Feige, Amin Saberi |
Santa Claus Meets Hypergraph Matchings. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Anup Rao 0001, David Zuckerman |
Extractors for Three Uneven-Length Sources. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, Simon Litsyn, Ning Xie 0002 |
Breaking the epsilon-Soundness Bound of the Linearity Test over GF(2). |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Kortsarz, Michael Langberg, Zeev Nutov |
Approximating Maximum Subgraphs without Short Cycles. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Cardinal, Eythan Levy |
Connected Vertex Covers in Dense Graphs. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
connected vertex cover, dense graph, approximation algorithm, vertex cover |
| 1 | Eli Ben-Sasson, Michael Viderman |
Tensor Products of Weakly Smooth Codes Are Robust. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Vikraman Arvind, Partha Mukhopadhyay |
Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Dan Gutfreund, Salil P. Vadhan |
Limitations of Hardness vs. Randomness under Uniform Reductions. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
derandomization, pseudorandom generators, black-box reductions |
| 1 | Martin Fürer, Shiva Prasad Kasiviswanathan |
Approximately Counting Embeddings into Random Graphs. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, James R. Lee, Avi Wigderson |
Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Avner Magen, Anastasios Zouzias |
Near Optimal Dimensionality Reductions That Preserve Volumes. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ashish Goel, Klaus Jansen, José D. P. Rolim, Ronitt Rubinfeld (eds.) |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Raphael Yuster |
Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Halman, Chung-Lun Li, David Simchi-Levi |
Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
time-cost tradeoff, approximation algorithms, Project management |
| 1 | Mihai Badoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, Morteza Zadimoghaddam |
Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom |
On the Query Complexity of Testing Orientations for Being Eulerian. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Lukasz Kowalik, Marcin Mucha |
Deterministic 7/8-Approximation for the Metric Maximum TSP. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | David P. Woodruff |
Corruption and Recovery-Efficient Locally Decodable Codes. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Matthew McCutchen, Samir Khuller |
Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
clustering, anonymity, streaming, outliers, k-center |
| 1 | MohammadAli Safari, Mohammad R. Salavatipour |
A Constant Factor Approximation for Minimum lambda-Edge-Connected k-Subgraph with Metric Costs. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | David R. Karger, Jacob Scott 0001 |
Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jeff Abrahamson, Béla Csaba, Ali Shokoufandeh |
Optimal Random Matchings on Trees and Applications. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
Random Matching, Hierarchically Separated Trees, Supremum Bounds |
| 1 | Dan Gutfreund, Guy N. Rothblum |
The Complexity of Local List Decoding. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
list-decodable codes, constant-depth circuits, locally-decodable codes |
| 1 | Thành Nguyen 0001 |
A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
ATSP, LP relaxation |
| 1 | Hariharan Narayanan, Partha Niyogi |
Sampling Hypersurfaces through Diffusion. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Blais |
Improved Bounds for Testing Juntas. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan |
Learning Random Monotone DNF. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Micah Adler, Brent Heeringa |
Approximating Optimal Binary Decision Trees. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Nutov |
Approximating Directed Weighted-Degree Constrained Networks. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Edo Liberty, Nir Ailon, Amit Singer |
Dense Fast Random Projections and Lean Walsh Transforms. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
Lean Walsh Transforms, Johnson Lindenstrauss, Dimension reduction, Random Projections |
| 1 | Venkatesan Guruswami, Prasad Raghavendra |
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Gregory B. Sorkin |
The Power of Choice in a Generalized Pólya Urn Model. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license