Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Venkatesan Guruswami, Sai Sandeep |
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms. |
APPROX-RANDOM |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Alexander Birx, Yann Disser, Kevin Schewior |
Improved Bounds for Open Online Dial-a-Ride on the Line. |
APPROX-RANDOM |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Michael Anastos, Alan M. Frieze |
On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs. |
APPROX-RANDOM |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Sagar Kale |
Small Space Stream Summary for Matroid Center. |
APPROX-RANDOM |
2019 |
DBLP DOI BibTeX RDF |
|
1 | Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, Kuan Yang |
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Sayan Bandyapadhyay, Neeraj Kumar 0004, Subhash Suri, Kasturi R. Varadarajan |
Improved Approximation Bounds for the Minimum Constraint Removal Problem. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Richard Santiago, F. Bruce Shepherd |
Multi-Agent Submodular Optimization. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Kuan Cheng, Xin Li 0006 |
Randomness Extraction in AC0 and with Small Locality. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Antonio Blanca, Zongchen Chen, Eric Vigoda |
Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Yonatan Nakar, Dana Ron |
On the Testability of Graph Partition Properties. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Maya Leshkowitz |
Round Complexity Versus Randomness Complexity in Interactive Proofs. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | William M. Hoza, Adam R. Klivans |
Preserving Randomness for Adaptive Algorithms. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Pasin Manurangsi, Luca Trevisan |
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Shyam Narayanan |
Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Tianyu Liu 0002 |
Torpid Mixing of Markov Chains for the Six-vertex Model on Z^2. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Corrie Jacobien Carstens, Pieter Kleer |
Speeding up Switch Markov Chains for Sampling Bipartite Graphs with Given Degree Sequence. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Tali Kaufman, Izhar Oppenheim |
High Order Random Walks: Beyond Spectral Gap. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Fotis Iliopoulos |
Commutative Algorithms Approximate the LLL-distribution. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Allan Borodin, Christodoulos Karavasilis, Denis Pankratov |
Greedy Bipartite Matching in Random Type Poisson Arrival Model. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Suvrit Sra, Nisheeth K. Vishnoi, Ozan Yildiz |
On Geodesically Convex Formulations for the Brascamp-Lieb Constant. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Hao-Ting Wei, Wing-Kai Hon, Paul Horn, Chung-Shou Liao, Kunihiko Sadakane |
An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Akanksha Agrawal 0001, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh 0001, Meirav Zehavi |
Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Amit Levi, Yuichi Yoshida |
Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Peter Gracar, Alexandre Stauffer |
Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Joseph Swernofsky |
Tensor Rank is Hard to Approximate. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, Daniel Vaz 0001 |
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Yi Li 0002, Vasileios Nakos, David P. Woodruff |
On Low-Risk Heavy Hitters and Sparse Recovery Schemes. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Igor Carboni Oliveira, Rahul Santhanam |
Pseudo-Derandomizing Learning and Approximation. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Goonwanth Reddy, Rahul Vaze |
Robust Online Speed Scaling With Deadline Uncertainty. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai |
Generalized Assignment of Time-Sensitive Item Groups. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Ray Li, Mary Wootters |
Improved List-Decodability of Random Linear Binary Codes. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Janardhan Kulkarni, Shi Li 0001 |
Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | László Babai, Timothy J. F. Black, Angela Wuu |
List-Decoding Homomorphism Codes with Arbitrary Codomains. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Xin Li 0006, Shachar Lovett, Jiapeng Zhang |
Sunflowers and Quasi-Sunflowers from Randomness Extractors. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Elena Grigorescu, Akash Kumar 0003, Karl Wimmer |
Flipping out with Many Flips: Hardness of Testing k-Monotonicity. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan 0001 |
Polar Codes with Exponentially Small Error at Finite Block Length. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Shai Vardi |
Randomly Coloring Graphs of Logarithmically Bounded Pathwidth. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | |
Front Matter, Table of Contents, Preface, Conference Organization. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Yi Li 0002, Vasileios Nakos |
Deterministic Heavy Hitters with Sublinear Query Time. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Rocco A. Servedio, Li-Yang Tan |
Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo |
Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Aditya Bhaskara, Srivatsan Kumar |
Low Rank Approximation in the Presence of Outliers. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Eden Chlamtác, Pasin Manurangsi |
Sherali-Adams Integrality Gaps Matching the Log-Density Threshold. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Eric Blais, Klaus Jansen, José D. P. Rolim, David Steurer (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA |
APPROX-RANDOM |
2018 |
DBLP BibTeX RDF |
|
1 | Valentine Kabanets, Zhenjian Lu |
Satisfiability and Derandomization for Small Polynomial Threshold Circuits. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Sajin Koroth, Or Meir |
Improved Composition Theorems for Functions and Relations. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Mark Braverman, Young Kun-Ko |
Semi-Direct Sum Theorem and Nearest Neighbor under l_infty. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Ishay Haviv |
On Minrank and Forbidden Subgraphs. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou |
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Michael Viderman |
Explicit Strong LTCs with Inverse Poly-Log Rate and Constant Soundness. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Chaoping Xing, Chen Yuan 0003 |
How Long Can Optimal Locally Repairable Codes Be?. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Amariah Becker |
A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Mark Bun, Justin Thaler |
Approximate Degree and the Complexity of Depth Three Circuits. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha |
Boolean Function Analysis on High-Dimensional Expanders. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Ryan O'Donnell, Yu Zhao 0032 |
On Closeness to k-Wise Uniformity. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Zhiyi Huang 0002, Ning Kang 0001, Zhihao Gavin Tang, Xiaowei Wu 0001, Yuhao Zhang 0001 |
Online Makespan Minimization: The Power of Restart. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Chandra Chekuri, Shalmoli Gupta |
Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Ishay Haviv |
On Minrank and the Lovász Theta Function. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Aditya Krishnan 0001, Sidhanth Mohanty, David P. Woodruff |
On Sketching the q to p Norms. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Anat Ganor, Karthik C. S. |
Communication Complexity of Correlated Equilibrium with Small Support. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Andreas Wiese |
Fixed-Parameter Approximation Schemes for Weighted Flowtime. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Aleksandrs Belovs |
Adaptive Lower Bound for Testing Monotonicity on the Line. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Tony Johansson |
The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | Talya Eden, Will Rosenbaum |
Lower Bounds for Approximating Graph Parameters via Communication Complexity. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
1 | L. Elisa Celis, Amit Deshpande 0001, Tarun Kathuria, Damian Straszak, Nisheeth K. Vishnoi |
On the Complexity of Constrained Determinantal Point Processes. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Haim Avron, Kenneth L. Clarkson, David P. Woodruff |
Sharper Bounds for Regularized Data Fitting. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Edo Liberty, Maxim Sviridenko |
Greedy Minimization of Weakly Supermodular Set Functions. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Rupam Acharyya, Daniel Stefankovic |
Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Thomas Kesselheim, Andreas Tönnis |
Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Alessandro Chiesa, Peter Manohar, Igor Shinkar |
On Axis-Parallel Tests for Tensor Product Codes. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | |
Frontmatter, Table of Contents, Preface, Organization, External Reviewers, List of Authors. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, Chao Xu 0002 |
Global and Fixed-Terminal Cuts in Digraphs. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan R. Ullman, Ali Vakilian, Anak Yodpinyanee |
Fractional Set Cover in the Streaming Model. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | S. Luna Frank-Fischer, Venkatesan Guruswami, Mary Wootters |
Locality via Partially Lifted Codes. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Ray Li |
Efficiently Decodable Codes for the Binary Deletion Channel. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi 0001, Chaitanya Swamy, Jens Vygen |
On the Integrality Gap of the Prize-Collecting Steiner Forest LP. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Samuel Haney, Bruce M. Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram |
Symmetric Interdiction for Matching Problems. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Thomas Watson 0001 |
Communication Complexity of Statistical Distance. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák |
When Are Welfare Guarantees Robust?. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Jess Banks, Robert Kleinberg, Cristopher Moore |
The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Noga Alon, Omri Ben-Eliezer |
Efficient Removal Lemmas for Matrices. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Alexander Golovnev, Oded Regev 0001, Omri Weinstein |
The Minrank of Random Graphs. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Gorav Jindal, Pavel Kolev, Richard Peng, Saurabh Sawlani |
Density Independent Algorithms for Sparsifying k-Step Random Walks. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Joshua Brakensiek |
Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Sagar Kale, Sumedh Tirodkar |
Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Sarah Cannon, David A. Levin, Alexandre Stauffer |
Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | David G. Harris 0001, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh |
A Lottery Model for Center-Type Problems with Outliers. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Arnab Bhattacharyya 0001, Sivakanth Gopi, Avishay Tal |
Lower Bounds for 2-Query LCCs over Large Alphabet. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Maciej Obremski, Maciej Skorski |
Renyi Entropy Estimation Revisited. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Jaroslaw Blasiok, Jian Ding, Jelani Nelson |
Continuous Monitoring of l_p Norms in Data Streams. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Klaus Jansen, José D. P. Rolim, David Williamson, Santosh S. Vempala (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA |
APPROX-RANDOM |
2017 |
DBLP BibTeX RDF |
|
1 | Cody R. Freitag, Eric Price 0001, William J. Swartworth |
Testing Hereditary Properties of Sequences. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Anupam Gupta 0001, Archit Karandikar |
Stochastic Unsplittable Flows. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Alan M. Frieze, Wesley Pegden |
Traveling in Randomly Embedded Random Graphs. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Omer Angel, Abbas Mehrabian, Yuval Peres |
The String of Diamonds Is Tight for Rumor Spreading. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Ilya Volkovich |
On Some Computations on Sparse Polynomials. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, Vivek Madan |
On the Expansion of Group-Based Lifts. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou |
Streaming Periodicity with Mismatches. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Michel X. Goemans, Francisco Unda |
Approximating Incremental Combinatorial Optimization Problems. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Amin Coja-Oghlan, Charilaos Efthymiou 0001, Nor Jaafari, Mihyun Kang, Tobias Kapetanopoulos |
Charting the Replica Symmetric Phase. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|