APPROX-RANDOM

Keyphrases

Publications

2021

David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov
A New Notion of Commutativity for the Algorithmic Lovász Local Lemma. APPROX-RANDOM (2021)
Umang Bhaskar, A. R. Sricharan, Rohit Vaish
On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. APPROX-RANDOM (2021)
Chandan Saha, Bhargav Thankey
Hitting Sets for Orbits of Circuit Classes and Polynomial Families. APPROX-RANDOM (2021)
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube. APPROX-RANDOM (2021)
Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos
A Constant-Factor Approximation for Weighted Bond Cover. APPROX-RANDOM (2021)
Front Matter, Table of Contents, Preface, Conference Organization. APPROX-RANDOM (2021)
Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz
Memory-Sample Lower Bounds for Learning Parity with Noise. APPROX-RANDOM (2021)
Anna Arutyunova, Anna Großwendt, Heiko Röglin, Melanie Schmidt, Julian Wargalla
Upper and Lower Bounds for Complete Linkage in General Metric Spaces. APPROX-RANDOM (2021)
Talya Eden, Saleet Mossel, Ronitt Rubinfeld
Sampling Multiple Edges Efficiently. APPROX-RANDOM (2021)
Sankeerth Rao Karingula, Shachar Lovett
Singularity of Random Integer Matrices with Large Entries. APPROX-RANDOM (2021)
Ralf Borndörfer, Katrin Casel, Davis Issac, Aikaterini Niklanovits, Stephan Schwartz, Ziena Zeif
Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs. APPROX-RANDOM (2021)
Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Kamyar Khodamoradi
Approximation Algorithms for Demand Strip Packing. APPROX-RANDOM (2021)
Kuikui Liu
From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk. APPROX-RANDOM (2021)
Uma Girish, Ran Raz, Wei Zhan
Lower Bounds for XOR of Forrelations. APPROX-RANDOM (2021)
Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal
Hardness of Approximation for Euclidean k-Median. APPROX-RANDOM (2021)
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
Decision Tree Heuristics Can Fail, Even in the Smoothed Setting. APPROX-RANDOM (2021)
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
Query Complexity of Global Minimum Cut. APPROX-RANDOM (2021)
Louis Golowich
Improved Product-Based High-Dimensional Expanders. APPROX-RANDOM (2021)
Anupam Gupta, Amit Kumar, Sahil Singla
Bag-Of-Tasks Scheduling on Related Machines. APPROX-RANDOM (2021)
Sepehr Assadi, Soheil Behnezhad
On the Robust Communication Complexity of Bipartite Matching. APPROX-RANDOM (2021)
Allan Borodin, Calum MacRury, Akash Rakheja
Secretary Matching Meets Probing with Commitment. APPROX-RANDOM (2021)
Sandip Banerjee, Rafail Ostrovsky, Yuval Rabani
Min-Sum Clustering (With Outliers). APPROX-RANDOM (2021)
Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan
Parallel Repetition for the GHZ Game: A Simpler Proof. APPROX-RANDOM (2021)
Chandra Chekuri, Kent Quanrud, Manuel R. Torres
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems. APPROX-RANDOM (2021)
Chien-Chung Huang, François Sellier
Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint. APPROX-RANDOM (2021)
Varsha Dani, Diksha Gupta, Thomas P. Hayes
On the Power of Choice for k-Colorability of Random Graphs. APPROX-RANDOM (2021)
Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz
General Knapsack Problems in a Dynamic Setting. APPROX-RANDOM (2021)
Reut Levi, Nadav Shoshan
Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs. APPROX-RANDOM (2021)
Ninad Rajgopal, Rahul Santhanam
On the Structure of Learnability Beyond P/Poly. APPROX-RANDOM (2021)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
The Swendsen-Wang Dynamics on Trees. APPROX-RANDOM (2021)
Brian Brubach, Nathaniel Grammel, David G. Harris, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti
Approximating Two-Stage Stochastic Supplier Problems. APPROX-RANDOM (2021)
Srikanth Srinivasan, S. Venkitesh
On the Probabilistic Degree of an n-Variate Boolean Function. APPROX-RANDOM (2021)
William M. Hoza
Better Pseudodistributions and Derandomization for Space-Bounded Computation. APPROX-RANDOM (2021)
Rikhav Shah, Sandeep Silwal
Smoothed Analysis of the Condition Number Under Low-Rank Perturbations. APPROX-RANDOM (2021)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
Fine-Grained Completeness for Optimization in P. APPROX-RANDOM (2021)
Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Interplay Between Graph Isomorphism and Earth Mover's Distance in the Query and Communication Worlds. APPROX-RANDOM (2021)
Yi Li, David P. Woodruff
The Product of Gaussian Matrices Is Close to Gaussian. APPROX-RANDOM (2021)
Omar Alrabiah, Venkatesan Guruswami
Visible Rank and Codes with Locality. APPROX-RANDOM (2021)
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan
Pseudorandom Generators for Read-Once Monotone Branching Programs. APPROX-RANDOM (2021)
Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan
Candidate Tree Codes via Pascal Determinant Cubes. APPROX-RANDOM (2021)
Rajesh Jayaram, John Kallaugher
An Optimal Algorithm for Triangle Counting in the Stream. APPROX-RANDOM (2021)
Rocco A. Servedio, Li-Yang Tan
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma. APPROX-RANDOM (2021)
Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
-Polynomials and Applications. APPROX-RANDOM (2021)
Kshipra Bhawalkar, Kostas Kollias, Manish Purohit
Revenue Maximization in Transportation Networks. APPROX-RANDOM (2021)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
Ideal-Theoretic Explanation of Capacity-Achieving Decoding. APPROX-RANDOM (2021)
Aditya Parulekar, Advait Parulekar, Eric Price
L1 Regression with Lewis Weights Subsampling. APPROX-RANDOM (2021)
Elena Grigorescu, Young-San Lin, Kent Quanrud
Online Directed Spanners and Steiner Forests. APPROX-RANDOM (2021)
Hossein Jowhari
An Estimator for Matching Size in Low Arboricity Graphs with Two Applications. APPROX-RANDOM (2021)
Susanne Albers, Sebastian Schubert
Optimal Algorithms for Online b-Matching with Variable Vertex Capacities. APPROX-RANDOM (2021)

volume 207, 2021

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference). APPROX-RANDOM 207 (2021)