| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 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 | 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 | Rohit Khandekar, Guy Kortsarz, Zeev Nutov |
Network-Design with Degree Constraints. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Ravishankar Krishnaswamy, Barna Saha |
On Capacitated Set Cover Problems. |
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 | Oded Goldreich 0001, Tali Kaufman |
Proximity Oblivious Testing and the Role of Invariances. |
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 | 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 | 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 | Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan 0001 |
On Sums of Locally Testable Affine Invariant Properties. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Thomas Watson 0001 |
Extractors and Lower Bounds for Locally Samplable Sources. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Arora, Rong Ge 0001 |
New Tools for Graph Coloring. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Lidor Avigad, Oded Goldreich 0001 |
Testing Graph Blow-Up. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhiyi Huang 0002, Sampath Kannan |
On Sampling from Multivariate Distributions. |
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 | 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 | Mohammed Amin Abdullah 0001, Colin Cooper, Moez Draief |
Viral Processes by Random Walks on Random Regular Graphs. |
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 | Shachar Lovett, Srikanth Srinivasan 0001 |
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 | Andris Ambainis, Andrew M. Childs, Yi-Kai Liu 0001 |
Quantum Property Testing for Bounded-Degree Graphs. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Madhu Sudan 0001 |
Limits on the Rate of Locally Testable Affine-Invariant Codes. |
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 | 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 | Per Austrin, Mark Braverman, Eden Chlamtac |
Inapproximability of NP-Complete Variants of Nash Equilibrium. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala |
Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions. |
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 | Khanh Do Ba, Piotr Indyk |
Sparse Recovery with Partial Support Knowledge. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan T. Chakaravarthy, Amit Kumar 0001, Vinayaka Pandit, Sambuddha Roy, Yogish Sabharwal |
Scheduling Resources for Throughput Maximization. |
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 | Daniel Kane 0001, Raghu Meka, Jelani Nelson |
Almost Optimal Explicit Johnson-Lindenstrauss Families. |
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 | Thomas Watson 0001 |
Query Complexity in Errorless Hardness Amplification. |
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 | Irit Dinur, Tali Kaufman |
Dense Locally Testable Codes Cannot Have Constant Rate and Distance. |
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 | Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna |
Social Welfare in One-Sided Matching Markets without Money. |
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 | Adrian Dumitrescu, Minghui Jiang 0001, János Pach |
Opaque Sets. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael S. Crouch, Andrew McGregor 0001 |
Periodicity and Cyclic Shifts via Linear Sketches. |
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 | Eldar Fischer, Eyal Rozenberg |
Inflatable Graph Properties and Natural Property Tests. |
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 | 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 | Tobias Friedrich 0001, Lionel Levine |
Fast Simulation of Large-Scale Growth Models. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Sándor P. Fekete, Tom Kamphans, Alexander Kröller, Joseph S. B. Mitchell, Christiane Schmidt 0001 |
Exploring and Triangulating a Region by a Swarm of Robots. |
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 | Michael Kapralov, Rina Panigrahy |
Multiplicative Approximations of Random Walk Transition Probabilities. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrew Drucker |
Efficient Probabilistically Checkable Debates. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Dana Dachman-Soled, Rocco A. Servedio |
A Canonical Form for Testing Boolean Function Properties. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhiyi Huang 0002, Lei Wang 0010, Yuan Zhou 0007 |
Black-Box Reductions in Mechanism Design. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Indyk, Stanislaw J. Szarek |
Almost-Euclidean Subspaces of l1N\ell_1^N via Tensor Products: A Simple Approach to Randomness Reduction. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | David P. Woodruff |
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. |
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 | David Steurer |
Improved Rounding for Parallel Repeated Unique Games. |
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 | MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Julián Mestre |
The Checkpoint Problem. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Elya Dolev, Dana Ron |
Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries. |
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 | Tali Kaufman, Michael Viderman |
Locally Testable vs. Locally Decodable Codes. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Lee-Ad Gottlieb, Tyler Neylon |
Matrix Sparsification and the Sparse Null Space Problem. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, Anastasios Zouzias |
Online Embeddings. |
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 | Arnab Bhattacharyya 0001, 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 | Atri Rudra, Steve Uurtamo |
Two Theorems on List Decoding - (Extended Abstract). |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Ishay Haviv, Oded Regev 0001 |
The Euclidean Distortion of Flat Tori. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani |
Improved Pseudorandom Generators for Depth 2 Circuits. |
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 | Alistair Sinclair, Dan Vilenchik |
Delaying Satisfiability for Random 2SAT. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Yusuke Kobayashi 0001 |
Improved Algorithm for the Half-Disjoint Paths Problem. |
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 | Lee-Ad Gottlieb, Robert Krauthgamer |
Proximity Algorithms for Nearly-Doubling Spaces. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Gruia Calinescu |
Min-Power Strong Connectivity. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan, Rocco A. Servedio |
Learning and Lower Bounds for AC0 with Threshold Gates. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody, Amit Chakrabarti, Oded Regev 0001, Thomas Vidick, Ronald de Wolf |
Better Gap-Hamming Lower Bounds via Better Round Elimination. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jop Briët, Sourav Chakraborty 0001, David García-Soriano, Arie Matsliah |
Monotonicity Testing and Shortest-Path Routing on the Cube. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Nayantara Bhatnagar, Allan Sly, Prasad Tetali |
Reconstruction Threshold for the Hardcore Model. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe 0001 |
Propagation Connectivity of Random Hypergraphs. |
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 | Thomas P. Hayes, Alistair Sinclair |
Liftings of Tree-Structured Markov Chains - (Extended Abstract). |
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 | Irit Dinur, Elazar Goldenberg |
The Structure of Winning Strategies in Parallel Repetition Games. |
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 | Ken-ichi Kawarabayashi, Yusuke Kobayashi 0001 |
An O(logn)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs. |
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 | Russell Impagliazzo, Valentine Kabanets |
Constructive Proofs of Concentration 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 |
|
| 1 | MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Morteza Zadimoghaddam |
Submodular Secretary Problem and Extensions. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuichi Yoshida, Hiro Ito |
Testing Outerplanarity of Bounded Degree Graphs. |
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 | Per Austrin |
Improved Inapproximability for Submodular Maximization. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikolaos Fountoulakis, Konstantinos Panagiotou |
Rumor Spreading on Random Regular Graphs and Expanders. |
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 | Thomas Watson 0001 |
Relativized Worlds without Worst-Case to Average-Case Reductions for NP. |
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 | Eli Ben-Sasson, Michael Viderman |
Low Rate Is Insufficient for Local Testability. |
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 | Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh |
Better Size Estimation for Sparse Matrix Products. |
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 | Oded Goldreich 0001 |
On Testing Computability by Small Width OBDDs. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license