| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Xi Chen 0001, Adam Freilich, Rocco A. Servedio, Timothy Sun |
Sample-Based High-Dimensional Convexity Testing.  |
APPROX-RANDOM  |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Rabani, Rakesh Venkat |
Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low Dimensional Spaces. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang 0001, Roger Wattenhofer |
Min-Cost Bipartite Perfect Matching with Delays. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee |
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Anna Ben-Hamou, Yuval Peres |
Cutoff for a Stratified Random Walk on the Hypercube. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Ameya Velingker, Santhoshini Velusamy |
Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Dean Doron, François Le Gall, Amnon Ta-Shma |
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen 0001, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten |
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus Jansen, Kim-Manuel Klein, Maria Kosche, Leon Ladewig |
Online Strip Packing with Polynomial Migration. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova |
Agnostic Learning from Tolerant Natural Proofs. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brakensiek, Venkatesan Guruswami |
The Quest for Strong Inapproximability Results with Perfect Completeness. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Vedat Levi Alev, Lap Chi Lau |
Approximating Unique Games Using Low Diameter Graph Decomposition. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Glencora Borradaile, Baigong Zheng |
A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Chien-Chung Huang, Naonori Kakimura, Yuichi Yoshida |
Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher S. Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, Yifeng Zhang |
Scheduling Problems over Network of Machines. |
APPROX-RANDOM |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Reut Levi, Dana Ron, Ronitt Rubinfeld |
A Local Algorithm for Constructing Spanners in Minor-Free Graphs. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Renjie Song, Yitong Yin, Jinman Zhao |
Counting Hypergraph Matchings up to Uniqueness Threshold. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Anup Rao 0001, Makrand Sinha |
A Direct-Sum Theorem for Read-Once Branching Programs. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Halman |
A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Sharath Raghvendra |
A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Samir Khuller, Sheng Yang 0005 |
Revisiting Connected Dominating Sets: An Optimal Local Algorithm? |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Sungjin Im, Janardhan Kulkarni, Benjamin Moseley, Kamesh Munagala |
A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnab Bhattacharyya 0001, Abhishek Bhowmick 0001, Chetan Gupta |
On Higher-Order Fourier Analysis over Non-Prime Fields. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Arturs Backurs, Anastasios Sidiropoulos |
Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan Hazla, Thomas Holenstein, Elchanan Mossel |
Lower Bounds on Same-Set Inner Product in Correlated Spaces. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Noah Stephens-Davidowitz |
Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Dana Moshkovitz, Govind Ramnarayan, Henry Yuen |
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ridwan Syed, Madhur Tulsiani |
Proving Weak Approximability Without Algorithms. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola |
Bounded Independence vs. Moduli. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Kortsarz, Zeev Nutov |
LP-Relaxations for Tree Augmentation. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Subhash Khot, Igor Shinkar |
An ~O(n) Queries Adaptive Tester for Unateness. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Eden Chlamtác, Michael Dinitz, Christian Konrad 0001, Guy Kortsarz, George Rabanca |
The Densest k-Subhypergraph Problem. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward |
A Bi-Criteria Approximation Algorithm for k-Means. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Anthony Kim, Vahid Liaghat, Junjie Qin, Amin Saberi |
Online Energy Storage Management: an Algorithmic Approach. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Prahladh Harsha, Srikanth Srinivasan 0001 |
On Polynomial Approximations to AC^0. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Dániel Marx, Ario Salmasi, Anastasios Sidiropoulos |
Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Pooya Hatami |
On the Structure of Quintic Polynomials. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Victor Bapst, Amin Coja-Oghlan |
The Condensation Phase Transition in the Regular k-SAT Model. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, Henrique Stagni |
Estimating Parameters Associated with Monotone Properties. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir Braverman, Alan Roytman, Gregory Vorsanger |
Approximating Subadditive Hadamard Functions on Implicit Matrices. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Dhruv Medarametla, Aaron Potechin |
Bounds on the Norms of Uniform Low Degree Graph Matrices. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Guillaume Chapuy, Guillem Perarnau |
Local Convergence and Stability of Tight Bridge-Addable Graph Classes. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Varun Kanade, Nikos Leonardos, Frédéric Magniez |
Stable Matching with Evolving Preferences. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Cyril Nicaud |
Fast Synchronization of Random Automata. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Amin Coja-Oghlan, Will Perkins 0001 |
Belief Propagation on Replica Symmetric Random Factor Graph Models. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Heng Guo 0001, Pinyan Lu |
Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronen Shaltiel, Jad Silbak |
Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Yitong Yin, Chihao Zhang 0001 |
Sampling in Potts Model on Sparse Random Graphs. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Michal Feldman, Inbal Talgam-Cohen |
Oblivious Rounding and the Integrality Gap. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Yi Li 0002, David P. Woodruff |
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk |
Hardness of Approximation for H-Free Edge Modification Problems. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryuhei Mori, David Witmer |
Lower Bounds for CSP Refutation by SDP Hierarchies. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernd Gärtner, Antonis Thomas |
The Niceness of Unique Sink Orientations. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Amitabh Basu, Michael Dinitz, Xin Li 0006 |
Computing Approximate PSD Factorizations. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael B. Cohen, Cameron Musco, Jakub Pachocki |
Online Row Sampling. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrew McGregor 0001, Sofya Vorotnikova |
Planar Matching in Streams Revisited. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan |
Near-Optimal UGC-hardness of Approximating Max k-CSP_R. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Esther Ezra, Shachar Lovett |
On the Beck-Fiala Conjecture for Random Set Systems. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov |
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Moses Charikar, Yonatan Naamad, Anthony Wirth |
On Approximating Target Set Selection. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Lin Chen 0009, Deshi Ye, Guochuan Zhang |
Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus Jansen, Claire Mathieu, José D. P. Rolim, Chris Umans (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France |
APPROX-RANDOM |
2016 |
DBLP BibTeX RDF |
|
| 1 | Jasine Babu, Areej Khoury, Ilan Newman |
Every Property of Outerplanar Graphs is Testable. |
APPROX-RANDOM |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova |
Tighter Connections between Derandomization and Circuit Lower Bounds. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Andreas Galanis, Daniel Stefankovic, Eric Vigoda |
Swendsen-Wang Algorithm on the Mean-Field Potts Model. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Viswanath Nagarajan, Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai, Joel L. Wolf |
The Container Selection Problem. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Zachary Drudi, Nicholas J. A. Harvey, Stephen Ingram, Andrew Warfield, Jake Wires |
Approximating Hit Rate Curves using Streaming Algorithms. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Elkin, Arnold Filtser, Ofer Neiman |
Terminal Embeddings. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev 0001, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright 0004 |
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernhard Haeupler, Pritish Kamath, Ameya Velingker |
Communication with Partial Noiseless Feedback. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir Braverman, Rafail Ostrovsky, Alan Roytman |
Zero-One Laws for Sliding Windows and Universal Sketches. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Frontmatter, Table of Contents, Preface, Program Commitees, External Reviewers, List of Authors. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, Hehui Wu |
Large Supports are Required for Well-Supported Nash Equilibria. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck |
Correlation in Hard Distributions in Communication Complexity. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Robin Kothari, David Racicot-Desloges, Miklos Santha |
Separating Decision Tree Complexity from Subcube Partition Complexity. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Ittai Abraham, Shiri Chechik, Robert Krauthgamer, Udi Wieder |
Approximate Nearest Neighbor Search in Metrics of Planar Graphs. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Fidaa Abed, Parinya Chalermsook, José Correa 0001, Andreas Karrenbauer, Pablo Pérez-Lantero, José A. Soto, Andreas Wiese |
On Guillotine Cutting Sequences. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Pasin Manurangsi, Dana Moshkovitz |
Approximating Dense Max 2-CSPs. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Jayadev Acharya, Clément L. Canonne, Gautam Kamath 0001 |
A Chasm Between Identity and Equivalence Testing with Conditional Queries. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Zachary Friggstad, Zhihan Gao 0002 |
On Linear Programming Relaxations for Unsplittable Flow in Trees. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Gil Cohen, Avishay Tal |
Two Structural Results for Low Degree Polynomials and Applications. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan |
Learning Circuits with few Negations. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Rong Ge 0001, Tengyu Ma 0001 |
Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Balthazar Bauer, Shay Moran, Amir Yehudayoff |
Internal Compression of Protocols to Entropy. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Shiva Prasad Kasiviswanathan, Mark Rudelson |
Spectral Norm of Random Kernel Matrices with Applications to Privacy. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, Pan Xu 0001 |
Improved Bounds in Stochastic Matching and Optimization. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Xiaoming Sun 0001, David P. Woodruff |
Tight Bounds for Graph Problems in Insertion Streams. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Sebastian Berndt 0001, Klaus Jansen, Kim-Manuel Klein |
Fully Dynamic Bin Packing Revisited . |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Hendrik Fichtenberger, Pan Peng 0001, Christian Sohler |
On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Euiwoong Lee |
Inapproximability of H-Transversal/Packing. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Bouke Cloostermans |
Minimizing Maximum Flow-time on Related Machines. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Victor Bapst, Amin Coja-Oghlan |
Harnessing the Bethe Free Energy. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Naveen Garg 0001, Klaus Jansen, Anup Rao 0001, José D. P. Rolim (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA |
APPROX-RANDOM |
2015 |
DBLP BibTeX RDF |
|
| 1 | Shiri Chechik, Edith Cohen, Haim Kaplan |
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Charilaos Efthymiou 0001 |
Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir Braverman, Stephen R. Chestnut |
Universal Sketches for the Frequency Negative Moments and Other Decreasing Streaming Sums. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Cygan, Tomasz Kociumaka |
Approximating Upper Degree-Constrained Partial Orientations. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilya Volkovich |
Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee |
Approximate Hypergraph Coloring under Low-discrepancy and Related Promises. |
APPROX-RANDOM |
2015 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license