Adaptive Sketches for Robust Regression with Importance Sampling (English)
Free access
- New search for: Mahabadi, Sepideh
- New search for: Woodruff, David P.
- New search for: Zhou, Samson
- Further information on Zhou, Samson:
-
https://orcid.org/0000-0001-8288-5698
- New search for: Mahabadi, Sepideh
- New search for: Woodruff, David P.
- New search for: Zhou, Samson
- Further information on Zhou, Samson:
-
https://orcid.org/0000-0001-8288-5698
- New search for: Chakrabarti, Amit
- Further information on Chakrabarti, Amit:
-
https://orcid.org/0000-0003-3633-9180
- New search for: Swamy, Chaitanya
- Further information on Swamy, Chaitanya:
-
https://orcid.org/0000-0003-1108-7941
In:
LIPIcs, Volume 245, APPROX/RANDOM 2022
: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
;
245
;
31:1-31:21
;
2022
-
ISBN:
-
ISSN:
- Conference paper / Electronic Resource
-
Title:Adaptive Sketches for Robust Regression with Importance Sampling
-
Contributors:Mahabadi, Sepideh ( author ) / Woodruff, David P. ( author ) / Zhou, Samson ( author ) / Chakrabarti, Amit ( editor ) / Swamy, Chaitanya ( editor )
-
Published in:LIPIcs, Volume 245, APPROX/RANDOM 2022 : Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) ; 245 ; 31:1-31:21Leibniz International Proceedings in Informatics (LIPIcs) ; 245 ; 31:1-31:21
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2022-09-15
-
Size:21 pages , 948917 byte
-
Remarks:LIPIcs, Vol. 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), pages 31:1-31:21
-
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
-
A Unified Approach to Discrepancy MinimizationBansal, Nikhil / Laddha, Aditi / Vempala, Santosh et al. | 2022
- 2
-
Fourier Growth of Regular Branching ProgramsLee, Chin Ho / Pyne, Edward / Vadhan, Salil et al. | 2022
- 3
-
Double Balanced Sets in High Dimensional ExpandersKaufman, Tali / Mass, David et al. | 2022
- 4
-
Fast and Perfect Sampling of Subgraphs and Polymer SystemsBlanca, Antonio / Cannon, Sarah / Perkins, Will et al. | 2022
- 5
-
High Dimensional Expansion Implies Amplified Local TestabilityKaufman, Tali / Oppenheim, Izhar et al. | 2022
- 6
-
Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary InputsGirish, Uma / Mittal, Kunal / Raz, Ran / Zhan, Wei et al. | 2022
- 7
-
Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in NetworksMehta, Hermish / Reichman, Daniel et al. | 2022
- 8
-
Beyond Single-Deletion Correcting Codes: Substitutions and TranspositionsGabrys, Ryan / Guruswami, Venkatesan / Ribeiro, João / Wu, Ke et al. | 2022
- 9
-
Affine Extractors and AC0-ParityHuang, Xuangui / Ivanov, Peter / Viola, Emanuele et al. | 2022
- 10
-
Hyperbolic Concentration, Anti-Concentration, and DiscrepancySong, Zhao / Zhang, Ruizhe et al. | 2022
- 11
-
Improved Local Testing for Multiplicity CodesKarliner, Dan / Ta-Shma, Amnon et al. | 2022
- 12
-
Unbalanced Expanders from Multiplicity CodesKalev, Itay / Ta-Shma, Amnon et al. | 2022
- 13
-
Streaming Algorithms with Large Approximation FactorsLi, Yi / Lin, Honghao / Woodruff, David P. / Zhang, Yuheng et al. | 2022
- 14
-
Local Stochastic Algorithms for Alignment in Self-Organizing Particle SystemsKedia, Hridesh / Oh, Shunhao / Randall, Dana et al. | 2022
- 15
-
Tight Chernoff-Like Bounds Under Limited IndependenceSkorski, Maciej et al. | 2022
- 16
-
Eigenstripping, Spectral Decay, and Edge-Expansion on PosetsGaitonde, Jason / Hopkins, Max / Kaufman, Tali / Lovett, Shachar / Zhang, Ruizhe et al. | 2022
- 17
-
Accelerating Polarization via Alphabet ExtensionDuursma, Iwan / Gabrys, Ryan / Guruswami, Venkatesan / Lin, Ting-Chun / Wang, Hsin-Po et al. | 2022
- 18
-
Sketching Distances in Monotone Graph ClassesEsperet, Louis / Harms, Nathaniel / Kupavskii, Andrey et al. | 2022
- 19
-
Communication Complexity of CollisionGöös, Mika / Jain, Siddhartha et al. | 2022
- 20
-
Range Avoidance for Low-Depth Circuits and Connections to PseudorandomnessGuruswami, Venkatesan / Lyu, Xin / Wang, Xiuhan et al. | 2022
- 21
-
Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate CaseBhargava, Vishwas / Garg, Ankit / Kayal, Neeraj / Saha, Chandan et al. | 2022
- 22
-
Lower Bound Methods for Sign-Rank and Their LimitationsHatami, Hamed / Hatami, Pooya / Pires, William / Tao, Ran / Zhao, Rosie et al. | 2022
- 23
-
Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial TimeArvind, V. / Chatterjee, Abhranil / Mukhopadhyay, Partha et al. | 2022
- 24
-
Sampling from Potts on Random Graphs of Unbounded Degree via Random-Cluster DynamicsBlanca, Antonio / Gheissari, Reza et al. | 2022
- 25
-
Improved Bounds for Randomly Colouring Simple HypergraphsFeng, Weiming / Guo, Heng / Wang, Jiaheng et al. | 2022
- 26
-
Lifting with Inner Functions of Polynomial DiscrepancyManor, Yahel / Meir, Or et al. | 2022
- 27
-
Exploring the Gap Between Tolerant and Non-Tolerant Distribution TestingChakraborty, Sourav / Fischer, Eldar / Ghosh, Arijit / Mishra, Gopinath / Sen, Sayantan et al. | 2022
- 28
-
A Sublinear Local Access Implementation for the Chinese Restaurant ProcessMörters, Peter / Sohler, Christian / Walzer, Stefan et al. | 2022
- 29
-
A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph ProcessGao, Pu / MacRury, Calum / Prałat, Paweł et al. | 2022
- 30
-
Cover and Hitting Times of Hyperbolic Random GraphsKiwi, Marcos / Schepers, Markus / Sylvester, John et al. | 2022
- 31
-
Adaptive Sketches for Robust Regression with Importance SamplingMahabadi, Sepideh / Woodruff, David P. / Zhou, Samson et al. | 2022
- 32
-
Finding the KT Partition of a Weighted Graph in Near-Linear TimeApers, Simon / Gawrychowski, Paweł / Lee, Troy et al. | 2022
- 33
-
Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream ModelFeldman, Moran / Szarf, Ariel et al. | 2022
- 34
-
Ordered k-Median with OutliersDeng, Shichuan / Zhang, Qianfan et al. | 2022
- 35
-
Sketching Approximability of (Weak) Monarchy PredicatesChou, Chi-Ning / Golovnev, Alexander / Shahrasbi, Amirbehshad / Sudan, Madhu / Velusamy, Santhoshini et al. | 2022
- 36
-
Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow SchedulingFukunaga, Takuro et al. | 2022
- 37
-
Fair Correlation Clustering in General GraphsSchwartz, Roy / Zats, Roded et al. | 2022
- 38
-
On Sketching Approximations for Symmetric Boolean CSPsBoyland, Joanna / Hwang, Michael / Prasad, Tarun / Singer, Noah / Velusamy, Santhoshini et al. | 2022
- 39
-
Massively Parallel Algorithms for Small Subgraph CountingBiswas, Amartya Shankha / Eden, Talya / Liu, Quanquan C. / Rubinfeld, Ronitt / Mitrović, Slobodan et al. | 2022
- 40
-
Hardness Results for Weaver’s Discrepancy ProblemSpielman, Daniel A. / Zhang, Peng et al. | 2022
- 41
-
Relative Survivable Network DesignDinitz, Michael / Koranteng, Ama / Kortsarz, Guy et al. | 2022
- 42
-
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique NumberGuruswami, Venkatesan / Kothari, Pravesh K. / Manohar, Peter et al. | 2022
- 43
-
Approximating CSPs with OutliersGhoshal, Suprovat / Louis, Anand et al. | 2022
- 44
-
Submodular Dominance and ApplicationsQiu, Frederick / Singla, Sahil et al. | 2022
- 45
-
Online Facility Location with Linear DelayBienkowski, Marcin / Böhm, Martin / Byrka, Jarosław / Marcinkowski, Jan et al. | 2022
- 46
-
Prophet Matching in the Probe-Commit ModelBorodin, Allan / MacRury, Calum / Rakheja, Akash et al. | 2022
- 47
-
The Biased Homogeneous r-Lin ProblemGhoshal, Suprovat et al. | 2022
- 48
-
Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph CountingAssadi, Sepehr / Nguyen, Hoai-An et al. | 2022
- 49
-
Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack ConstraintKlimm, Max / Knaack, Martin et al. | 2022
- 50
-
Some Results on Approximability of Minimum Sum Vertex CoverStanković, Aleksa et al. | 2022
- 51
-
(1+ε)-Approximate Shortest Paths in Dynamic StreamsElkin, Michael / Trehan, Chhaya et al. | 2022
- 52
-
Caching with ReservesIbrahimpur, Sharat / Purohit, Manish / Svitkina, Zoya / Vee, Erik / Wang, Joshua R. et al. | 2022
- 53
-
Space Optimal Vertex Cover in Dynamic StreamsNaidu, Kheeran K. / Shah, Vihan et al. | 2022
- 54
-
Approximating LCS and Alignment Distance over Multiple SequencesDas, Debarati / Saha, Barna et al. | 2022
- 55
-
A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 GraphsFriedrich, Tobias / Issac, Davis / Kumar, Nikhil / Mallek, Nadym / Zeif, Ziena et al. | 2022