Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat |
On Fortification of Projection Games. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Kathrin Skubch |
The Minimum Bisection in the Planted Bisection Model. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright 0004 |
Improved NP-Inapproximability for 2-Variable Linear Equations. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Euiwoong Lee |
Towards a Characterization of Approximation Resistance for Symmetric CSPs. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Michael A. Forbes 0001, Venkatesan Guruswami |
Dimension Expanders via Rank Condensers. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Elchanan Mossel, Sébastien Roch |
Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Michael Dinitz, Robert Krauthgamer, Tal Wagner |
Towards Resistance Sparsifiers. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Anna Adamaszek, Parinya Chalermsook, Andreas Wiese |
How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Julia Chuzhoy, David H. K. Kim |
On Approximating Node-Disjoint Paths in Grids. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Lin Chen 0009, Nicole Megow, Roman Rischke, Leen Stougie |
Stochastic and Robust Scheduling in the Cloud. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa |
A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Joshua Brody, Mario Sánchez |
Dependent Random Graphs and Multi-Party Pointer Jumping. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | David Felber, Rafail Ostrovsky |
A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Mark Bun, Thomas Steinke 0002 |
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Siyao Guo, Ilan Komargodski |
Negation-Limited Formulas. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | David Adjiashvili |
Non-Uniform Robust Network Design in Planar Graphs. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Antonio Blanca, Alistair Sinclair |
Dynamics for the Mean-field Random-cluster Model. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | David G. Harris 0001, Francis Sullivan |
Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Amin Coja-Oghlan, Charilaos Efthymiou 0001, Nor Jaafari |
Local Convergence of Random Graph Colorings. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Carol Wang |
Deletion Codes in the High-noise and High-rate Regimes. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Nikhil Bansal 0001, Anupam Gupta 0001, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, Clifford Stein 0001 |
A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi 0001, Ravi Sundaram |
Designing Overlapping Networks for Publish-Subscribe Systems. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Arkadev Chattopadhyay, Michael E. Saks |
The Power of Super-logarithmic Number of Players. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Adam R. Klivans, Pravesh Kothari |
Embedding Hard Learning Problems Into Gaussian Space. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Amit Deshpande 0001, Rakesh Venkat |
Guruswami-Sinop Rounding without Higher Level Lasserre. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Andreas Emil Feldmann, Jochen Könemann, Neil Olver, Laura Sanità |
On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Kshipra Bhawalkar, Sreenivas Gollapudi, Debmalya Panigrahi |
Online Set Cover with Set Requests. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad R. Salavatipour, Chaitanya Swamy |
Approximation Algorithms for Minimum-Load k-Facility Location. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Vladimir Braverman, Jonathan Katzman, Charles Seidell, Gregory Vorsanger |
An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Prasad Raghavendra, Tselil Schramm |
Gap Amplification for Small-Set Expansion via Random Walks. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Suguru Tamaki, Yuichi Yoshida |
Robust Approximation of Temporal CSP. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Anat Ganor, Ran Raz |
Space Pseudorandom Generators by Communication Complexity Lower Bounds. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Oded Goldreich 0001 |
On Multiple Input Problems in Property Testing. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Gábor Braun, Samuel Fiorini, Sebastian Pokutta |
Average Case Polyhedral Complexity of the Maximum Stable Set Problem. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Eric Blais, Joshua Brody, Badih Ghazi |
The Information Complexity of Hamming Distance. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, Dan Vilenchik |
The Condensation Phase Transition in Random Graph Coloring. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Nicholas J. A. Harvey, Roy Schwartz 0002, Mohit Singh |
Discrepancy Without Partial Colorings. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Flavio Chierichetti, Anirban Dasgupta 0001, Ravi Kumar 0001, Silvio Lattanzi |
On Reconstructing a Hidden Permutation. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Chaitanya Swamy |
Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Noga Alon, Troy Lee, Adi Shraibman |
The Cover Number of a Matrix and its Algorithmic Applications. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Shanfei Li |
An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Chandan K. Dubey, Thomas Holenstein |
Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Julia Böttcher, Jan Hladký, Diana Piguet, Anusch Taraz |
An Approximate Version of the Tree Packing Conjecture via Random Embeddings. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Hu Fu 0001, Robert D. Kleinberg |
Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Eden Chlamtác, Michael Dinitz |
Lowest Degree k-Spanner: Approximation and Hardness. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | |
Frontmatter, Table of Contents, Preface, Conference Organization. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo 0001, Mark Jerrum, Daniel Stefankovic, Eric Vigoda |
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Ittai Abraham, Shiri Chechik, Kunal Talwar |
Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Alan J. Soper, Vitaly A. Strusevich |
Power of Preemption on Uniform Parallel Machines. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Moran Feldman, Rani Izsak |
Constrained Monotone Function Maximization and the Supermodular Degree. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Alan Guo, Madhu Sudan 0001 |
List Decoding Group Homomorphisms Between Supersolvable Groups. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Stavros G. Kolliopoulos, Yannis Moysoglou |
Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Varun Kanade, Elchanan Mossel, Tselil Schramm |
Global and Local Information in Clustering Labeled Block Models. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Martin Gairing, Tobias Harks, Max Klimm |
Complexity and Approximation of the Continuous Network Design Problem. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Anand Louis, Yury Makarychev |
Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Tsz Chiu Kwok, Lap Chi Lau |
Lower Bounds on Expansions of Graph Powers. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Shlomo Jozeph |
Universal Factor Graphs for Every NP-Hard Boolean CSP. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | T. S. Jayram, Jan Vondrák |
Exchangeability and Realizability: De Finetti Theorems on Graphs. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, Cristopher Moore (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain |
APPROX-RANDOM |
2014 |
DBLP BibTeX RDF |
|
1 | Abhiram Natarajan, Yi Wu 0002 |
Computational Complexity of Certifying Restricted Isometry Property. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Josep Díaz, Leslie Ann Goldberg, David Richerby, Maria J. Serna |
Absorption Time of the Moran Process. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Alina Ene, Jan Vondrák |
Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Nathanaël François, Rahul Jain 0001, Frédéric Magniez |
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Reut Levi, Dana Ron, Ronitt Rubinfeld |
Local Algorithms for Sparse Spanning Graphs. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Raghu Meka, Omer Reingold, Yuan Zhou 0007 |
Deterministic Coupon Collection and Better Strong Dispersers. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Adrian Dumitrescu, Minghui Jiang 0001, Csaba D. Tóth |
Computing Opaque Interior Barriers à la Shermer. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Shashi Mittal, Andreas S. Schulz, Sebastian Stiller |
Robust Appointment Scheduling. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Michal Feldman, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg |
Reaching Consensus via Non-Bayesian Asynchronous Learning in Social Networks. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Jingcheng Liu 0001, Pinyan Lu, Chihao Zhang 0001 |
The Complexity of Ferromagnetic Two-spin Systems with External Fields. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Michael Krivelevich, Daniel Reichman 0001, Wojciech Samotij |
Smoothed Analysis on Connected Graphs. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Takuro Fukunaga, Afshin Nikzad, R. Ravi 0001 |
Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Cenny Wenner |
Parity is Positively Useless. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Andreas Galanis, Daniel Stefankovic, Eric Vigoda, Linji Yang |
Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Abbas Mehrabian, Nick Wormald |
It's a Small World for Random Surfers. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Jeremy Karp, R. Ravi 0001 |
A 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Thomas Steinke 0002, Salil P. Vadhan, Andrew Wan |
Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Gil Cohen, Anat Ganor, Ran Raz |
Two Sides of the Coin Problem. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Michael Dinitz, Guy Kortsarz, Zeev Nutov |
Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Milan Bradonjic, Will Perkins 0001 |
On Sharp Thresholds in Random Geometric Graphs. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Carol Wang |
Evading Subspaces Over Large Fields and Explicit List-decodable Rank-metric Codes. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Michael S. Crouch, Daniel M. Stubbs |
Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Siddharth Barman, Shuchi Chawla 0001, Seeun Umboh |
Network Design with Coverage Costs. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev |
Certifying Equality With Limited Interaction. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Mika Göös, Thomas Watson 0001 |
Communication Complexity of Set-Disjointness for All Probabilities. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Christoph Hansknecht, Max Klimm, Alexander Skopalik |
Approximate Pure Nash Equilibria in Weighted Congestion Games. |
APPROX-RANDOM |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Feng Pan 0005, Aaron Schild |
Interdiction Problems on Planar Graphs. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Elena Grigorescu, Karl Wimmer, Ning Xie 0002 |
Tight Lower Bounds for Testing Linear Isomorphism. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Zeev Dvir, Guangda Hu |
Matching-Vector Families and LDCs over Large Modulo. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Yonatan Goldhirsh, Michael Viderman |
Testing Membership in Counter Automaton Languages. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Anupam Gupta 0001, Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber |
The Approximability of the Binary Paintshop Problem. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Omer Reingold, Thomas Steinke 0002, Salil P. Vadhan |
Pseudorandomness for Regular Branching Programs via Fourier Analysis. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Kook Jin Ahn, Sudipto Guha, Andrew McGregor 0001 |
Spectral Sparsification in Dynamic Graph Streams. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Antonio Blanca, David J. Galvin, Dana Randall, Prasad Tetali |
Phase Coexistence and Slow Mixing for the Hard-Core Model on ℤ2. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Lucia Batman, Russell Impagliazzo, Cody Murray, Ramamohan Paturi |
Finding Heavy Hitters from Lossy or Noisy Data. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Katherine Edwards, Simon Griffiths, William Sean Kennedy |
Partial Interval Set Cover - Trade-Offs between Scalability and Optimality. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Shi Li 0001, Srivatsan Narayanan |
Capacitated Network Design on Undirected Graphs. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Dominik Scheder, Li-Yang Tan |
On the Average Sensitivity and Density of k-CNF Formulas. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Amos Beimel, Kobbi Nissim, Uri Stemmer |
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos |
A Pseudo-approximation for the Genus of Hamiltonian Graphs. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Sudipto Guha, Kamesh Munagala |
Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback. |
APPROX-RANDOM |
2013 |
DBLP DOI BibTeX RDF |
|