default search action
24th RANDOM / 23rd APPROX 2020 [Virtual Conference]
- Jaroslaw Byrka
, Raghu Meka:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference. LIPIcs 176, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2020, ISBN 978-3-95977-164-1 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:20
- Divesh Aggarwal, Siyao Guo, Maciej Obremski, João Ribeiro
Extractor Lower Bounds, Revisited. 1:1-1:20 - Kwangjun Ahn
A Simpler Strong Refutation of Random k-XOR. 2:1-2:15 - Sarah Miracle, Amanda Pascoe Streib, Noah Streib:
Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains. 3:1-3:21 - Zeyu Guo
Improved Explicit Hitting-Sets for ROABPs. 4:1-4:16 - Nader H. Bshouty:
Almost Optimal Testers for Concise Representations. 5:1-5:20 - Noga Alon, Sepehr Assadi:
Palette Sparsification Beyond (Δ+1) Vertex Coloring. 6:1-6:22 - Dean Doron
On Hitting-Set Generators for Polynomials That Vanish Rarely. 7:1-7:23 - Markus Bläser, Anurag Pandey:
Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness. 8:1-8:13 - Venkatesan Guruswami, Ray Li, Jonathan Mosheiff
Bounds for List-Decoding and List-Recovery of Random Linear Codes. 9:1-9:21 - Ronen Shaltiel:
Is It Possible to Improve Yao's XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle? 10:1-10:20 - Catherine S. Greenhill, Bernard Mans
Balanced Allocation on Dynamic Hypergraphs. 11:1-11:22 - Jeff M. Phillips, Wai Ming Tai:
The GaussianSketch for Almost Relative Error Kernel Distance. 12:1-12:20 - Eric Price, Jonathan Scarlett:
A Fast Binary Splitting Approach to Non-Adaptive Group Testing. 13:1-13:20 - Jan Dreier
Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size. 14:1-14:13 - Shuichi Hirahara, Osamu Watanabe:
On Nonadaptive Security Reductions of Hitting Set Generators. 15:1-15:14 - Artur Czumaj, Hendrik Fichtenberger
Testable Properties in General Graphs and Random Order Streaming. 16:1-16:20 - Calvin Beideman, Karthekeyan Chandrasekaran, Chao Xu:
Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs. 17:1-17:21 - Eric Blais, Abhinav Bommireddi:
On Testing and Robust Characterizations of Convexity. 18:1-18:15 - Reut Levi
Distributed Testing of Graph Isomorphism in the CONGEST Model. 19:1-19:24 - Linh V. Tran, Van Vu:
Reaching a Consensus on Random Networks: The Power of Few. 20:1-20:15 - Sumegha Garg, Pravesh K. Kothari, Ran Raz
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. 21:1-21:18 - Amit Chakrabarti
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. 22:1-22:23 - Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
Disjointness Through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. 23:1-23:15 - Clément L. Canonne, Karl Wimmer:
Testing Data Binnings. 24:1-24:13 - Tali Kaufman, Ella Sharakanski:
Chernoff Bound for High-Dimensional Expanders. 25:1-25:22 - Cyrus Rashtchian, David P. Woodruff, Hanlin Zhu:
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems. 26:1-26:20 - Dana Ron
Almost Optimal Distribution-Free Sample-Based Testing of k-Modality. 27:1-27:19 - Shalev Ben-David, Mika Göös, Robin Kothari
When Is Amplification Necessary for Composition in Randomized Query Complexity? 28:1-28:16 - Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar:
On Multilinear Forms: Bias, Correlation, and Tensor Rank. 29:1-29:23 - Ben Lund
On the List Recoverability of Randomly Punctured Codes. 30:1-30:11 - Sayan Bandyapadhyay
On Perturbation Resilience of Non-Uniform k-Center. 31:1-31:22 - Fedor V. Fomin
Low-Rank Binary Matrix Approximation in Column-Sum Norm. 32:1-32:18 - Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak
Pinning down the Strong Wilber 1 Bound for Binary Search Trees. 33:1-33:21 - Venkatesan Guruswami
Revisiting Alphabet Reduction in Dinur's PCP. 34:1-34:14 - Tatiana Starikovskaya, Michal Svagerka, Przemyslaw Uznanski
Lp Pattern Matching in a Stream. 35:1-35:23 - Karine Chubarian, Anastasios Sidiropoulos:
Computing Bi-Lipschitz Outlier Embeddings into the Line. 36:1-36:21 - Nicole Megow
Online Minimum Cost Matching with Recourse on the Line. 37:1-37:16 - Amey Bhangale, Diptarka Chakraborty, Rajendra Kumar:
Hardness of Approximation of (Multi-)LCS over Small Alphabet. 38:1-38:16 - Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit
On Approximating Degree-Bounded Network Design Problems. 39:1-39:21 - Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep:
Permutation Strikes Back: The Power of Recourse in Online Metric Matching. 40:1-40:20 - Eden Chlamtác
How to Cut a Ball Without Separating: Improved Approximations for Length Bounded Cut. 41:1-41:17 - Xiangyu Guo, Janardhan Kulkarni, Shi Li, Jiayi Xian:
On the Facility Location Problem in Online and Dynamic Models. 42:1-42:23 - Ishan Agarwal, Oded Regev, Yi Tang:
Nearly Optimal Embeddings of Flat Tori. 43:1-43:14 - Waldo Gálvez
A Tight (3/2+ε) Approximation for Skewed Strip Packing. 44:1-44:18 - Bohan Fan, Diego Ihara
Learning Lines with Ordinal Constraints. 45:1-45:15 - Shay Golan
Improved Circular k-Mismatch Sketches. 46:1-46:24 - Arindam Khan, Madhusudhan Reddy Pittu:
On Guillotine Separability of Squares and Rectangles. 47:1-47:22 - Lior Ben Yamin, Jing Li, Kanthi K. Sarpatwar
Maximizing Throughput in Flow Shop Real-Time Scheduling. 48:1-48:18 - Dor Katzelnick, Roy Schwartz:
Maximizing the Correlation: Extending Grothendieck's Inequality to Large Domains. 49:1-49:18 - Alexandr Andoni, Collin Burns, Yi Li
Streaming Complexity of SVMs. 50:1-50:22 - Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, Prafullkumar Tale
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs. 51:1-51:19 - Joanna Chybowska-Sokól
Online Coloring of Short Intervals. 52:1-52:18 - Roy Schwartz, Yotam Sharoni:
Approximating Requirement Cut via a Configuration LP. 53:1-53:16 - Sébastien Bubeck, Yuval Rabani:
Parametrized Metrical Task Systems. 54:1-54:14 - Syamantak Das, Lavina Jain, Nikhil Kumar:
A Constant Factor Approximation for Capacitated Min-Max Tree Cover. 55:1-55:13 - Nima Anari
An Extension of Plücker Relations with Applications to Subdeterminant Maximization. 56:1-56:16 - Buddhima Gamlath, Vadim Grinberg:
Approximating Star Cover Problems. 57:1-57:19 - Neng Huang
On the Approximability of Presidential Type Predicates. 58:1-58:20 - Sean Hallgren, Eunou Lee, Ojas Parekh:
An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem. 59:1-59:18 - Alexander Wei:
Better and Simpler Learning-Augmented Online Caching. 60:1-60:17 - Sylvia C. Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. 61:1-61:12 - Chien-Chung Huang, Theophile Thiery, Justin Ward:
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints. 62:1-62:19 - Chun-Hsiang Chan, Bundit Laekhanukit
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs. 63:1-63:20 - Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff:
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. 64:1-64:22
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-12-16 22:14 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: