default search action
APPROX/RANDOM 2022 [Virtual Conference]
- Amit Chakrabarti
, Chaitanya Swamy
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference). LIPIcs 245, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022, ISBN 978-3-95977-249-5 - Nikhil Bansal, Aditi Laddha, Santosh S. Vempala:
A Unified Approach to Discrepancy Minimization. 1:1-1:22 - Chin Ho Lee, Edward Pyne, Salil P. Vadhan:
Fourier Growth of Regular Branching Programs. 2:1-2:21 - Tali Kaufman, David Mass:
Double Balanced Sets in High Dimensional Expanders. 3:1-3:17 - Antonio Blanca, Sarah Cannon, Will Perkins:
Fast and Perfect Sampling of Subgraphs and Polymer Systems. 4:1-4:18 - Tali Kaufman, Izhar Oppenheim
High Dimensional Expansion Implies Amplified Local Testability. 5:1-5:10 - Uma Girish, Kunal Mittal, Ran Raz
Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs. 6:1-6:17 - Hermish Mehta, Daniel Reichman:
Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks. 7:1-7:17 - Ryan Gabrys
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. 8:1-8:17 - Xuangui Huang, Peter Ivanov, Emanuele Viola:
Affine Extractors and AC0-Parity. 9:1-9:14 - Zhao Song, Ruizhe Zhang:
Hyperbolic Concentration, Anti-Concentration, and Discrepancy. 10:1-10:19 - Dan Karliner, Amnon Ta-Shma:
Improved Local Testing for Multiplicity Codes. 11:1-11:19 - Itay Kalev, Amnon Ta-Shma
Unbalanced Expanders from Multiplicity Codes. 12:1-12:14 - Yi Li
Streaming Algorithms with Large Approximation Factors. 13:1-13:23 - Hridesh Kedia, Shunhao Oh, Dana Randall
Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems. 14:1-14:20 - Maciej Skorski
Tight Chernoff-Like Bounds Under Limited Independence. 15:1-15:14 - Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang:
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets. 16:1-16:24 - Iwan M. Duursma
Accelerating Polarization via Alphabet Extension. 17:1-17:15 - Louis Esperet
Sketching Distances in Monotone Graph Classes. 18:1-18:23 - Mika Göös, Siddhartha Jain
Communication Complexity of Collision. 19:1-19:9 - Venkatesan Guruswami, Xin Lyu, Xiuhan Wang:
Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness. 20:1-20:21 - Vishwas Bhargava
Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case. 21:1-21:22 - Hamed Hatami, Pooya Hatami
Lower Bound Methods for Sign-Rank and Their Limitations. 22:1-22:24 - Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay:
Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time. 23:1-23:22 - Antonio Blanca, Reza Gheissari:
Sampling from Potts on Random Graphs of Unbounded Degree via Random-Cluster Dynamics. 24:1-24:15 - Weiming Feng
Improved Bounds for Randomly Colouring Simple Hypergraphs. 25:1-25:17 - Yahel Manor, Or Meir
Lifting with Inner Functions of Polynomial Discrepancy. 26:1-26:17 - Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen:
Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing. 27:1-27:23 - Peter Mörters
A Sublinear Local Access Implementation for the Chinese Restaurant Process. 28:1-28:18 - Pu Gao, Calum MacRury, Pawel Pralat:
A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process. 29:1-29:22 - Marcos Kiwi
Cover and Hitting Times of Hyperbolic Random Graphs. 30:1-30:19 - Sepideh Mahabadi, David P. Woodruff, Samson Zhou
Adaptive Sketches for Robust Regression with Importance Sampling. 31:1-31:21 - Simon Apers, Pawel Gawrychowski, Troy Lee:
Finding the KT Partition of a Weighted Graph in Near-Linear Time. 32:1-32:14 - Moran Feldman
Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model. 33:1-33:24 - Shichuan Deng, Qianfan Zhang:
Ordered k-Median with Outliers. 34:1-34:22 - Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
Sketching Approximability of (Weak) Monarchy Predicates. 35:1-35:17 - Takuro Fukunaga
Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling. 36:1-36:13 - Roy Schwartz, Roded Zats:
Fair Correlation Clustering in General Graphs. 37:1-37:19 - Joanna Boyland
On Sketching Approximations for Symmetric Boolean CSPs. 38:1-38:23 - Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, Slobodan Mitrovic:
Massively Parallel Algorithms for Small Subgraph Counting. 39:1-39:28 - Daniel A. Spielman, Peng Zhang:
Hardness Results for Weaver's Discrepancy Problem. 40:1-40:14 - Michael Dinitz, Ama Koranteng, Guy Kortsarz:
Relative Survivable Network Design. 41:1-41:19 - Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. 42:1-42:7 - Suprovat Ghoshal, Anand Louis:
Approximating CSPs with Outliers. 43:1-43:16 - Frederick Qiu, Sahil Singla:
Submodular Dominance and Applications. 44:1-44:21 - Marcin Bienkowski
Online Facility Location with Linear Delay. 45:1-45:17 - Allan Borodin, Calum MacRury, Akash Rakheja:
Prophet Matching in the Probe-Commit Model. 46:1-46:24 - Suprovat Ghoshal:
The Biased Homogeneous r-Lin Problem. 47:1-47:14 - Sepehr Assadi, Hoai-An Nguyen:
Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting. 48:1-48:20 - Max Klimm, Martin Knaack:
Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint. 49:1-49:19 - Aleksa Stankovic
Some Results on Approximability of Minimum Sum Vertex Cover. 50:1-50:16 - Michael Elkin
(1+ε)-Approximate Shortest Paths in Dynamic Streams. 51:1-51:23 - Sharat Ibrahimpur
Caching with Reserves. 52:1-52:16 - Kheeran K. Naidu
Space Optimal Vertex Cover in Dynamic Streams. 53:1-53:15 - Debarati Das, Barna Saha:
Approximating LCS and Alignment Distance over Multiple Sequences. 54:1-54:21 - Tobias Friedrich
A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs. 55:1-55:18
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-15 19:45 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: