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

Lovett, Shachar

  1. Improved bounds for the sunflower lemma
    2019/08/22 by Ryan Alweiss, Alweiss, Ryan, Shachar Lovett +5 · 18 citations
    Mathematics · Computer Science · Engineering · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #graph theory and CDMA systems
  2. Constructive Discrepancy Minimization by Walking on The Edges
    2012/03/26 by Lovett, Shachar, Meka, Raghu · 9 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  3. Bilinear Classes: A Structural Framework for Provable Generalization in\n RL
    2021/03/19 by Simon S. Du, Du, Simon S., Sham M. Kakade +12 · 10 citations
    Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Adversarial Robustness in Machine Learning #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Reinforcement Learning in Robotics
  4. Worst Case to Average Case Reductions for Polynomials
    2008/06/27 by Tali Kaufman, Kaufman, Tali, Shachar Lovett +1 · 7 citations
    Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #FOS: Mathematics
  5. New Lower Bounds for Matching Vector Codes
    2012/04/05 by Bhowmick, Abhishek, Dvir, Zeev, Lovett, Shachar · 3 citations
    #68Q17 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  6. Variety Evasive Sets
    2012/03/20 by Zeev Dvir, Dvir, Zeev, Janós Kollár +3 · 3 citations
    Computer Science · Engineering · Mathematics · #Algebraic Geometry (math.AG) #Coding theory and cryptography #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
  7. New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
    2023/11/15 by Amir Abboud, Nick Fischer, Abboud, Amir +7 · 8 citations
    Computer Science · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems
  8. Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
    2016/12/13 by Dadush, Daniel, Garg, Shashwat, Lovett, Shachar +1 · 3 citations
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Probability (math.PR)
  9. Active classification with comparison queries
    2017/04/11 by Daniel M. Kane, Shachar Lovett, Kane, Daniel M. +5 · 3 citations
    Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms
  10. Communication is bounded by root of rank
    2013/06/08 by Lovett, Shachar · 3 citations
    #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
  11. Every locally characterized affine-invariant property is testable
    2012/12/16 by Arnab Bhattacharyya, Bhattacharyya, Arnab, Eldar Fischer +7 · 2 citations
    Computer Science · #Coding theory and cryptography #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation
  12. On the Beck-Fiala Conjecture for Random Set Systems
    2015/11/02 by Ezra, Esther, Lovett, Shachar · 2 citations
    #Combinatorics (math.CO) #FOS: Mathematics
  13. The Power of Comparisons for Actively Learning Linear Classifiers
    2019/07/08 by Max Hopkins, Daniel M. Kane, Hopkins, Max +3 · 4 citations
    Computer Science · #68Q32 #Algorithms and Data Compression #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification
  14. The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
    2017/08/03 by Bansal, Nikhil, Dadush, Daniel, Garg, Shashwat +1 · 3 citations
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  15. Point Location and Active Learning: Learning Halfspaces Almost Optimally
    2020/04/23 by Hopkins, Max, Kane, Daniel M., Lovett, Shachar +1 · 2 citations
    #68Q32 #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
  16. Sampling Equilibria: Fast No-Regret Learning in Structured Games
    2022/01/26 by Daniel Beaglehole, Max Hopkins, Beaglehole, Daniel +7 · 2 citations
    Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Adversarial Robustness in Machine Learning #Bayesian Modeling and Causal Inference #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Multiagent Systems (cs.MA)
  17. Inverse Conjecture for the Gowers norm is false
    2007/11/21 by Lovett, Shachar, Meshulam, Roy, Samorodnitsky, Alex · 1 citation
    #11T06 #Combinatorics (math.CO) #FOS: Mathematics
  18. Equivalence of polynomial conjectures in additive combinatorics
    2010/01/19 by Shachar Lovett, Lovett, Shachar · 1 citation
    Computer Science · Mathematics · #05B10 #11B13 #Advanced Graph Theory Research #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)
  19. Testing Low Complexity Affine-Invariant Properties
    2012/01/01 by Arnab Bhattacharyya, Eldar Fischer, Bhattacharyya, Arnab +3 · 1 citation
    Computer Science · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Software Testing and Debugging Techniques #VLSI and Analog Circuit Testing
  20. A Tail Bound for Read-k Families of Functions
    2012/04/25 by Gavinsky, Dmytro, Lovett, Shachar, Saks, Michael +1 · 1 citation
    #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
  21. Exponential Hardness of Reinforcement Learning with Linear Function Approximation
    2023/02/25 by Daniel M. Kane, Kane, Daniel, Sihan Liu +9 · 2 citations
    Computer Science · #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Reinforcement Learning in Robotics
  22. List decoding Reed-Muller codes over small fields
    2014/07/13 by Bhowmick, Abhishek, Lovett, Shachar · 1 citation
    #11T71 #68P30 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT)
  23. Bias vs structure of polynomials in large fields, and applications in information theory
    2015/06/05 by Bhowmick, Abhishek, Lovett, Shachar · 1 citation
    #11C08 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)
  24. Explicit separations between randomized and deterministic Number-on-Forehead communication
    2023/08/23 by Kelley, Zander, Lovett, Shachar, Meka, Raghu · 2 citations
    #68Q11 #68Q17 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #F.1.3 #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics
  25. Generalized comparison trees for point-location problems
    2018/04/23 by Daniel M. Kane, Shachar Lovett, Kane, Daniel M +3 · 1 citation
    Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning and Algorithms #Robotics and Sensor-Based Localization
  26. MDS matrices over small fields: A proof of the GM-MDS conjecture
    2018/03/07 by Lovett, Shachar · 1 citation
    #11T71 #68P30 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #E.4 #FOS: Computer and information sciences #FOS: Mathematics
  27. From DNF compression to sunflower theorems via regularity
    2019/03/01 by Shachar Lovett, Lovett, Shachar, Noam Solomon +3 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  28. Noise-tolerant, Reliable Active Classification with Comparison Queries
    2020/01/15 by Max Hopkins, Daniel M. Kane, Hopkins, Max +5 · 1 citation
    Computer Science · #68Q32 #Algorithms and Data Compression #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification
  29. Approximate union closed conjecture
    2022/11/21 by Zachary Chase, Shachar Lovett, Chase, Zachary +1 · 1 citation
    Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
  30. Streaming Lower Bounds and Asymmetric Set-Disjointness
    2023/01/13 by Shachar Lovett, Jiapeng Zhang, Lovett, Shachar +1 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
  31. Log-rank and lifting for AND-functions
    2020/10/18 by Knop, Alexander, Lovett, Shachar, McGuire, Sam +1 · 1 citation
    #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
  32. Quasipolynomial bounds for the corners theorem
    2025/04/09 by Michael Jaber, Yang P. Liu, Jaber, Michael +7 · 3 citations
    Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)