vix.ing · top · new · best · stats · spec

Waingarten, Erik

  1. Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness
    2017/02/22 by Xi Chen, Erik Waingarten, Chen, Xi +3 · 4 citations
    Computer Science · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Cryptography and Data Security
  2. Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
    2019/11/17 by Canonne, Clément L., Chen, Xi, Kamath, Gautam +2 · 4 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Probability (math.PR) #Statistics Theory (math.ST)
  3. The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction
    2022/05/01 by Moses Charikar, Erik Waingarten, Charikar, Moses +1 · 3 citations
    Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques
  4. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs
    2018/05/03 by Levi, Amit, Waingarten, Erik · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  5. Settling the query complexity of non-adaptive junta testing
    2017/04/20 by Chen, Xi, Servedio, Rocco A., Tan, Li-Yang +2 · 2 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  6. Nearly optimal edge estimation with independent set queries
    2019/07/09 by Chen, Xi, Levi, Amit, Waingarten, Erik · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  7. A Near-Linear Time Algorithm for the Chamfer Distance
    2023/07/06 by Ainesh Bakshi, Bakshi, Ainesh, Piotr Indyk +7 · 3 citations
    Computer Science · #Advanced Neural Network Applications #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graphics (cs.GR) #Machine Learning (cs.LG)
  8. New Streaming Algorithms for High Dimensional EMD and MST
    2021/11/05 by Chen, Xi, Jayaram, Rajesh, Levi, Amit +1 · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  9. A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
    2024/01/04 by Moses Charikar, Charikar, Moses, Michael Kapralov +3 · 3 citations
    Engineering · Mathematics · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Approximation and Integration #Nuclear Physics and Applications #Nuclear reactor physics and engineering
  10. Streaming Euclidean MST to a Constant Factor
    2022/12/13 by Vincent Cohen-Addad, Xi Chen, Cohen-Addad, Vincent +7 · 2 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  11. Approximate Near Neighbors for General Symmetric Norms
    2016/11/18 by Andoni, Alexandr, Nguyen, Huy L., Nikolov, Aleksandar +2 · 1 citation
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Metric Geometry (math.MG)
  12. Learning and Testing Junta Distributions with Subcube Conditioning
    2020/04/26 by Chen, Xi, Jayaram, Rajesh, Levi, Amit +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Probability (math.PR) #Statistics Theory (math.ST)
  13. Boolean Unateness Testing with \widetildeO(n3/4) Adaptive Queries
    2017/08/19 by Xi Chen, Chen, Xi, Erik Waingarten +3 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Machine Learning and Algorithms
  14. Data-Dependent LSH for the Earth Mover's Distance
    2024/03/08 by Rajesh Jayaram, Jayaram, Rajesh, Erik Waingarten +3 · 1 citation
    Earth and Planetary Sciences · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #GNSS positioning and interference #Geophysics and Gravity Measurements #Inertial Sensor and Navigation
  15. Testing Unateness Nearly Optimally
    2019/04/10 by Chen, Xi, Waingarten, Erik · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  16. Lower Bounds for Convexity Testing
    2024/10/23 by Xin Chen, Chen, Xi, Anindya De +7 · 2 citations
    Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
  17. Fast Algorithms for a New Relaxation of Optimal Transport
    2023/07/14 by Moses Charikar, Beidi Chen, Charikar, Moses +5 · 1 citation
    Computer Science · Mathematics · #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
  18. Instance-Optimal Uniformity Testing and Tracking
    2025/08/04 by Guy Blanc, Blanc, Guy, Clément L. Canonne +3 · 1 voice · 1 citation
    Computer Science · Decision Sciences · #Machine Learning and Algorithms #Optimization and Search Problems #Advanced Bandit Algorithms Research
  19. Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
    2025/02/22 by Chakrabarty, Deeparnab, Chen, Xi, Ristic, Simeon +2 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Statistics Theory (math.ST)