| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Dana Dachman-Soled, Rocco A. Servedio |
A Canonical Form for Testing Boolean Function Properties.  |
APPROX-RANDOM  |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wootters |
Public Key Locally Decodable Codes with Short Keys. |
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 | Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman |
Bandwidth and Low Dimensional Embedding. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak |
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Tali Kaufman |
Dense Locally Testable Codes Cannot Have Constant Rate and Distance. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody, David P. Woodruff |
Streaming Algorithms with One-Sided Estimation. |
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 | Zhiyi Huang, Lei Wang 0010, Yuan Zhou |
Black-Box Reductions in Mechanism Design. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Erik D. Demaine, Morteza Zadimoghaddam |
O(1)-Approximations for Maximum Movement Problems. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan T. Chakaravarthy, Amit Kumar, Vinayaka Pandit, Sambuddha Roy, Yogish Sabharwal |
Scheduling Resources for Throughput Maximization. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala |
Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions. |
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 | Khanh Do Ba, Piotr Indyk |
Sparse Recovery with Partial Support Knowledge. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Moran Feldman, Joseph Naor, Roy Schwartz |
Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract). |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Kapralov, Rina Panigrahy |
Multiplicative Approximations of Random Walk Transition Probabilities. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Thomas Watson |
Extractors and Lower Bounds for Locally Samplable Sources. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Tobias Friedrich, Lionel Levine |
Fast Simulation of Large-Scale Growth Models. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohammed Abdullah, Colin Cooper, Moez Draief |
Viral Processes by Random Walks on Random Regular Graphs. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Sergei Artemenko, Ronen Shaltiel |
Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrew Drucker |
Efficient Probabilistically Checkable Debates. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Sushant Sachdeva, Rishi Saket |
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Carol Wang |
Optimal Rate List Decoding via Derivative Codes. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel M. Kane, Raghu Meka, Jelani Nelson |
Almost Optimal Explicit Johnson-Lindenstrauss Families. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan |
On Sums of Locally Testable Affine Invariant Properties. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna |
Social Welfare in One-Sided Matching Markets without Money. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, Linji Yang |
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal, Ravishankar Krishnaswamy, Barna Saha |
On Capacitated Set Cover Problems. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Mark Braverman, Eden Chlamtac |
Inapproximability of NP-Complete Variants of Nash Equilibrium. |
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, 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 | Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein |
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Tali Kaufman |
Proximity Oblivious Testing and the Role of Invariances. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Domingos Dellamonica Jr., Subrahmanyam Kalyanasundaram, Daniel M. Martin, Vojtech Rödl, Asaf Shapira |
A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Sarah Miracle, Dana Randall, Amanda Pascoe Streib |
Clustering in Interfering Binary Mixtures. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Dana Ron, Gilad Tsur |
On Approximating the Number of Relevant Variables in a Function. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Madhu Sudan |
Limits on the Rate of Locally Testable Affine-Invariant Codes. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Lidor Avigad, Oded Goldreich |
Testing Graph Blow-Up. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael S. Crouch, Andrew McGregor |
Periodicity and Cyclic Shifts via Linear Sketches. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel |
The Computational Complexity of Estimating MCMC Convergence Time. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Nachshon Cohen, Zeev Nutov |
A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Arora, Rong Ge |
New Tools for Graph Coloring. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Feodor F. Dragan, Ekkehard Köhler |
An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Adrian Dumitrescu, Minghui Jiang, János Pach |
Opaque Sets. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhiyi Huang, Sampath Kannan |
On Sampling from Multivariate Distributions. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Maurice Cheung, David B. Shmoys |
A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Andris Ambainis, Andrew M. Childs, Yi-Kai Liu |
Quantum Property Testing for Bounded-Degree Graphs. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Eyal Rozenberg |
Inflatable Graph Properties and Natural Property Tests. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Tim Carnes, David B. Shmoys |
Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Rohit Khandekar, Guy Kortsarz, Zeev Nutov |
Network-Design with Degree Constraints. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Parinya Chalermsook |
Coloring and Maximum Independent Set of Rectangles. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Shachar Lovett, Srikanth Srinivasan |
Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 - o(1) Symmetric Gates. |
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 | 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. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Satisfying Degree-d Equations over GF[2] n. |
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 |
|
| 1 | Inge Li Gørtz, Viswanath Nagarajan |
Locating Depots for Capacitated Vehicle Routing. |
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 | Thomas Watson |
Query Complexity in Errorless Hardness Amplification. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Gruia Calinescu |
Min-Power Strong Connectivity. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson |
Approximating Linear Threshold Predicates. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Hyung-Chan An, Robert D. Kleinberg, David B. Shmoys |
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Guyslain Naves, Nicolas Sonnerat, Adrian Vetta |
Maximum Flows on Disjoint Paths. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Igor Gorodezky, Robert D. Kleinberg, David B. Shmoys, Gwen Spencer |
Improved Lower Bounds for the Universal and a priori TSP. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohit Singh, Kunal Talwar |
Improving Integrality Gaps via Chvátal-Gomory Rounding. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Sofya Raskhodnikova |
Approximation Algorithms for Min-Max Generalization Problems. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Subhash Khot, Preyas Popat, Rishi Saket |
Approximate Lasserre Integrality Gap for Unique Games. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Lee-Ad Gottlieb, Robert Krauthgamer |
Proximity Algorithms for Nearly-Doubling Spaces. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Eric Blais |
Testing Boolean Function Isomorphism. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Prasad Chebolu, Leslie Ann Goldberg, Russell A. Martin |
The Complexity of Approximately Counting Stable Matchings. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jop Briët, Sourav Chakraborty, David García-Soriano, Arie Matsliah |
Monotonicity Testing and Shortest-Path Routing on the Cube. |
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 | Thomas P. Hayes, Alistair Sinclair |
Liftings of Tree-Structured Markov Chains - (Extended Abstract). |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | MohammadHossein Bateni, Julia Chuzhoy |
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Elazar Goldenberg |
The Structure of Winning Strategies in Parallel Repetition Games. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Valentine Kabanets |
Constructive Proofs of Concentration Bounds. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Spyros C. Kontogiannis, Paul G. Spirakis |
Exploiting Concavity in Bimatrix Games: New Polynomially Tractable Subclasses. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Suguru Tamaki, Yuichi Yoshida |
A Query Efficient Non-adaptive Long Code Test with Perfect Completeness. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh |
Better Size Estimation for Sparse Matrix Products. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | David Steurer |
Improved Rounding for Parallel Repeated Unique Games. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Igor Shinkar |
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Atri Rudra, Steve Uurtamo |
Two Theorems on List Decoding - (Extended Abstract). |
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 | Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès |
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf |
Better Gap-Hamming Lower Bounds via Better Round Elimination. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich |
On Testing Computability by Small Width OBDDs. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Evdokia Nikolova |
Approximation Algorithms for Reliable Stochastic Combinatorial Optimization. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff |
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe |
Propagation Connectivity of Random Hypergraphs. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, Michael Viderman |
Locally Testable vs. Locally Decodable Codes. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Roy Kasher, Julia Kempe |
Two-Source Extractors Secure against Quantum Adversaries. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Julián Mestre |
The Checkpoint Problem. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Michael Viderman |
Low Rate Is Insufficient for Local Testability. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin |
Improved Inapproximability for Submodular Maximization. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Morteza Zadimoghaddam |
Submodular Secretary Problem and Extensions. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Yusuke Kobayashi |
Improved Algorithm for the Half-Disjoint Paths Problem. |
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 |
How to Schedule When You Have to Buy Your Energy. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Vikraman Arvind, Fengming Wang |
Uniform Derandomization from Pathetic Lower Bounds. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Frank Kammer, Torsten Tholey, Heiko Voepel |
Approximation Algorithms for Intersection Graphs. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")