On Testing and Robust Characterizations of Convexity (English)
Free access
- New search for: Blais, Eric
- New search for: Bommireddi, Abhinav
- New search for: Blais, Eric
- New search for: Bommireddi, Abhinav
- New search for: Byrka, Jarosław
- Further information on Byrka, Jarosław:
-
https://orcid.org/0000-0002-3387-0913
- New search for: Meka, Raghu
In:
LIPIcs, Volume 176, APPROX/RANDOM 2020
: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
;
176
;
18:1-18:15
;
2020
-
ISBN:
-
ISSN:
- Conference paper / Electronic Resource
-
Title:On Testing and Robust Characterizations of Convexity
-
Contributors:Blais, Eric ( author ) / Bommireddi, Abhinav ( author ) / Byrka, Jarosław ( editor ) / Meka, Raghu ( editor )
-
Published in:LIPIcs, Volume 176, APPROX/RANDOM 2020 : Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) ; 176 ; 18:1-18:15Leibniz International Proceedings in Informatics (LIPIcs) ; 176 ; 18:1-18:15
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2020-08-11
-
Size:15 pages , 518161 byte
-
Remarks:LIPIcs, Vol. 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), pages 18:1-18:15
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Conference paper
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Licence:
-
Source:
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
Extractor Lower Bounds, RevisitedAggarwal, Divesh / Guo, Siyao / Obremski, Maciej / Ribeiro, João / Stephens-Davidowitz, Noah et al. | 2020
- 2
-
A Simpler Strong Refutation of Random k-XORAhn, Kwangjun et al. | 2020
- 3
-
Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov ChainsMiracle, Sarah / Streib, Amanda Pascoe / Streib, Noah et al. | 2020
- 4
-
Improved Explicit Hitting-Sets for ROABPsGuo, Zeyu / Gurjar, Rohit et al. | 2020
- 5
-
Almost Optimal Testers for Concise RepresentationsBshouty, Nader H. et al. | 2020
- 6
-
Palette Sparsification Beyond (Δ+1) Vertex ColoringAlon, Noga / Assadi, Sepehr et al. | 2020
- 7
-
On Hitting-Set Generators for Polynomials That Vanish RarelyDoron, Dean / Ta-Shma, Amnon / Tell, Roei et al. | 2020
- 8
-
Polynomial Identity Testing for Low Degree Polynomials with Optimal RandomnessBläser, Markus / Pandey, Anurag et al. | 2020
- 9
-
Bounds for List-Decoding and List-Recovery of Random Linear CodesGuruswami, Venkatesan / Li, Ray / Mosheiff, Jonathan / Resch, Nicolas / Silas, Shashwat / Wootters, Mary et al. | 2020
- 10
-
Is It Possible to Improve Yao’s XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle?Shaltiel, Ronen et al. | 2020
- 11
-
Balanced Allocation on Dynamic HypergraphsGreenhill, Catherine / Mans, Bernard / Pourmiri, Ali et al. | 2020
- 12
-
The GaussianSketch for Almost Relative Error Kernel DistancePhillips, Jeff M. / Tai, Wai Ming et al. | 2020
- 13
-
A Fast Binary Splitting Approach to Non-Adaptive Group TestingPrice, Eric / Scarlett, Jonathan et al. | 2020
- 14
-
Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic SizeDreier, Jan / Kuinke, Philipp / Rossmanith, Peter et al. | 2020
- 15
-
On Nonadaptive Security Reductions of Hitting Set GeneratorsHirahara, Shuichi / Watanabe, Osamu et al. | 2020
- 16
-
Testable Properties in General Graphs and Random Order StreamingCzumaj, Artur / Fichtenberger, Hendrik / Peng, Pan / Sohler, Christian et al. | 2020
- 17
-
Multicriteria Cuts and Size-Constrained k-Cuts in HypergraphsBeideman, Calvin / Chandrasekaran, Karthekeyan / Xu, Chao et al. | 2020
- 18
-
On Testing and Robust Characterizations of ConvexityBlais, Eric / Bommireddi, Abhinav et al. | 2020
- 19
-
Distributed Testing of Graph Isomorphism in the CONGEST ModelLevi, Reut / Medina, Moti et al. | 2020
- 20
-
Reaching a Consensus on Random Networks: The Power of FewTran, Linh / Vu, Van et al. | 2020
- 21
-
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRGGarg, Sumegha / Kothari, Pravesh K. / Raz, Ran et al. | 2020
- 22
-
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear SketchesChakrabarti, Amit / Ghosh, Prantar / Thaler, Justin et al. | 2020
- 23
-
Disjointness Through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and BeyondBhattacharya, Anup / Chakraborty, Sourav / Ghosh, Arijit / Mishra, Gopinath / Paraashar, Manaswi et al. | 2020
- 24
-
Testing Data BinningsCanonne, Clément L. / Wimmer, Karl et al. | 2020
- 25
-
Chernoff Bound for High-Dimensional ExpandersKaufman, Tali / Sharakanski, Ella et al. | 2020
- 26
-
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph ProblemsRashtchian, Cyrus / Woodruff, David P. / Zhu, Hanlin et al. | 2020
- 27
-
Almost Optimal Distribution-Free Sample-Based Testing of k-ModalityRon, Dana / Rosin, Asaf et al. | 2020
- 28
-
When Is Amplification Necessary for Composition in Randomized Query Complexity?Ben-David, Shalev / Göös, Mika / Kothari, Robin / Watson, Thomas et al. | 2020
- 29
-
On Multilinear Forms: Bias, Correlation, and Tensor RankBhrushundi, Abhishek / Harsha, Prahladh / Hatami, Pooya / Kopparty, Swastik / Kumar, Mrinal et al. | 2020
- 30
-
On the List Recoverability of Randomly Punctured CodesLund, Ben / Potukuchi, Aditya et al. | 2020
- 31
-
On Perturbation Resilience of Non-Uniform k-CenterBandyapadhyay, Sayan et al. | 2020
- 32
-
Low-Rank Binary Matrix Approximation in Column-Sum NormFomin, Fedor V. / Golovach, Petr A. / Panolan, Fahad / Simonov, Kirill et al. | 2020
- 33
-
Pinning down the Strong Wilber 1 Bound for Binary Search TreesChalermsook, Parinya / Chuzhoy, Julia / Saranurak, Thatchaphol et al. | 2020
- 34
-
Revisiting Alphabet Reduction in Dinur’s PCPGuruswami, Venkatesan / Opršal, Jakub / Sandeep, Sai et al. | 2020
- 35
-
L_p Pattern Matching in a StreamStarikovskaya, Tatiana / Svagerka, Michal / Uznański, Przemysław et al. | 2020
- 36
-
Computing Bi-Lipschitz Outlier Embeddings into the LineChubarian, Karine / Sidiropoulos, Anastasios et al. | 2020
- 37
-
Online Minimum Cost Matching with Recourse on the LineMegow, Nicole / Nölke, Lukas et al. | 2020
- 38
-
Hardness of Approximation of (Multi-)LCS over Small AlphabetBhangale, Amey / Chakraborty, Diptarka / Kumar, Rajendra et al. | 2020
- 39
-
On Approximating Degree-Bounded Network Design ProblemsGuo, Xiangyu / Kortsarz, Guy / Laekhanukit, Bundit / Li, Shi / Vaz, Daniel / Xian, Jiayi et al. | 2020
- 40
-
Permutation Strikes Back: The Power of Recourse in Online Metric MatchingGupta, Varun / Krishnaswamy, Ravishankar / Sandeep, Sai et al. | 2020
- 41
-
How to Cut a Ball Without Separating: Improved Approximations for Length Bounded CutChlamtáč, Eden / Kolman, Petr et al. | 2020
- 42
-
On the Facility Location Problem in Online and Dynamic ModelsGuo, Xiangyu / Kulkarni, Janardhan / Li, Shi / Xian, Jiayi et al. | 2020
- 43
-
Nearly Optimal Embeddings of Flat ToriAgarwal, Ishan / Regev, Oded / Tang, Yi et al. | 2020
- 44
-
A Tight (3/2+ε) Approximation for Skewed Strip PackingGálvez, Waldo / Grandoni, Fabrizio / Ameli, Afrouz Jabal / Jansen, Klaus / Khan, Arindam / Rau, Malin et al. | 2020
- 45
-
Learning Lines with Ordinal ConstraintsFan, Bohan / Ihara, Diego / Mohammadi, Neshat / Sgherzi, Francesco / Sidiropoulos, Anastasios / Valizadeh, Mina et al. | 2020
- 46
-
Improved Circular k-Mismatch SketchesGolan, Shay / Kociumaka, Tomasz / Kopelowitz, Tsvi / Porat, Ely / Uznański, Przemysław et al. | 2020
- 47
-
On Guillotine Separability of Squares and RectanglesKhan, Arindam / Pittu, Madhusudhan Reddy et al. | 2020
- 48
-
Maximizing Throughput in Flow Shop Real-Time SchedulingBen Yamin, Lior / Li, Jing / Sarpatwar, Kanthi / Schieber, Baruch / Shachnai, Hadas et al. | 2020
- 49
-
Maximizing the Correlation: Extending Grothendieck’s Inequality to Large DomainsKatzelnick, Dor / Schwartz, Roy et al. | 2020
- 50
-
Streaming Complexity of SVMsAndoni, Alexandr / Burns, Collin / Li, Yi / Mahabadi, Sepideh / Woodruff, David P. et al. | 2020
- 51
-
On the Parameterized Approximability of Contraction to Classes of Chordal GraphsGunda, Spoorthy / Jain, Pallavi / Lokshtanov, Daniel / Saurabh, Saket / Tale, Prafullkumar et al. | 2020
- 52
-
Online Coloring of Short IntervalsChybowska-Sokół, Joanna / Gutowski, Grzegorz / Junosza-Szaniawski, Konstanty / Mikos, Patryk / Polak, Adam et al. | 2020
- 53
-
Approximating Requirement Cut via a Configuration LPSchwartz, Roy / Sharoni, Yotam et al. | 2020
- 54
-
Parametrized Metrical Task SystemsBubeck, Sébastien / Rabani, Yuval et al. | 2020
- 55
-
A Constant Factor Approximation for Capacitated Min-Max Tree CoverDas, Syamantak / Jain, Lavina / Kumar, Nikhil et al. | 2020
- 56
-
An Extension of Plücker Relations with Applications to Subdeterminant MaximizationAnari, Nima / Vuong, Thuy-Duong et al. | 2020
- 57
-
Approximating Star Cover ProblemsGamlath, Buddhima / Grinberg, Vadim et al. | 2020
- 58
-
On the Approximability of Presidential Type PredicatesHuang, Neng / Potechin, Aaron et al. | 2020
- 59
-
An Approximation Algorithm for the MAX-2-Local Hamiltonian ProblemHallgren, Sean / Lee, Eunou / Parekh, Ojas et al. | 2020
- 60
-
Better and Simpler Learning-Augmented Online CachingWei, Alexander et al. | 2020
- 61
-
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral CaseBoyd, Sylvia / Cheriyan, Joseph / Cummings, Robert / Grout, Logan / Ibrahimpur, Sharat / Szigeti, Zoltán / Wang, Lu et al. | 2020
- 62
-
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid ConstraintsHuang, Chien-Chung / Thiery, Theophile / Ward, Justin et al. | 2020
- 63
-
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite GraphsChan, Chun-Hsiang / Laekhanukit, Bundit / Wei, Hao-Ting / Zhang, Yuhao et al. | 2020
- 64
-
Weighted Maximum Independent Set of Geometric Objects in Turnstile StreamsBakshi, Ainesh / Chepurko, Nadiia / Woodruff, David P. et al. | 2020