Yehudayoff, Amir
- A Characterization of Multiclass Learnability
2022/03/03 by Nataly Brukhim, Brukhim, Nataly, Daniel Carmon +7 · 9 citations
Engineering · Computer Science · Medicine · #Artificial Immune Systems Applications #Rough Sets and Fuzzy Logic #Tuberculosis Research and Epidemiology
- A Theory of Universal Learning
2020/11/09 by Bousquet, Olivier, Hanneke, Steve, Moran, Shay +2 · 8 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)
- Sharp Isoperimetric Inequalities for Affine Quermassintegrals
2020/05/10 by Emanuel Milman, Milman, Emanuel, Amir Yehudayoff +1 · 5 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Diffusion and Search Dynamics #FOS: Mathematics #Functional Analysis (math.FA) #Metric Geometry (math.MG) #Point processes and geometric inequalities
- Sign rank versus VC dimension
2015/03/26 by Noga Alon, Shay Moran, Alon, Noga +3 · 3 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Machine Learning and Algorithms
- Sample compression schemes for VC classes
2015/03/24 by Shay Moran, Amir Yehudayoff, Moran, Shay +1 · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms
- Geometric stability via information theory
2015/09/29 by Ellis, David, Friedgut, Ehud, Kindler, Guy +1 · 3 citations
#05D99 #52C07 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #Information Theory (cs.IT) #Metric Geometry (math.MG)
- Learners that Use Little Information
2017/10/14 by Raef Bassily, Shay Moran, Bassily, Raef +7 · 6 citations
Computer Science · #Artificial Intelligence (cs.AI) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Privacy-Preserving Technologies in Data
- Rank Bounds for Design Matrices with Applications to Combinatorial\n Geometry and Locally Correctable Codes
2010/09/22 by Boaz Barak, Zeev Dvir, Barak, Boaz +5 · 2 citations
Computer Science · Engineering · #Coding theory and cryptography #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #graph theory and CDMA systems
- Containing Internal Diffusion Limited Aggregation
2011/11/02 by Hugo Duminil‐Copin, Duminil-Copin, Hugo, Cyrille Lucas +5 · 2 citations
Mathematics · #FOS: Mathematics #Geometry and complex manifolds #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics
- Local Borsuk-Ulam, Stability, and Replicability
2023/11/02 by Chase, Zachary, Chornomaz, Bogdan, Moran, Shay +1 · 5 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #I.2.6 #Machine Learning (cs.LG)
- Homogeneous formulas and symmetric polynomials
2009/07/15 by Pavel Hrubeš, Amir Yehudayoff, Hrubes, Pavel +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #graph theory and CDMA systems
- Grounded Lipschitz functions on trees are typically flat
2013/05/14 by Ron Peled, Wojciech Samotij, Peled, Ron +3 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistical Methods and Inference #Stochastic processes and statistical mechanics
- Inequalities and tail bounds for elementary symmetric polynomial with applications
2014/02/14 by Parikshit Gopalan, Amir Yehudayoff, Gopalan, Parikshit +1 · 1 citation
Computer Science · #68Q87 #68W20 #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Cryptography and Data Security #FOS: Computer and information sciences
- On statistical learning via the lens of compression
2016/10/12 by Ofir David, David, Ofir, Shay Moran +3 · 1 citation
Computer Science · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Imbalanced Data Classification Techniques #Logic (math.LO) #Logic in Computer Science (cs.LO) #Machine Learning (cs.LG) #Machine Learning and Algorithms
- The Sample Complexity Of ERMs In Stochastic Convex Optimization
2023/11/09 by Daniel Carmon, Roi Livni, Carmon, Daniel +3 · 2 citations
Computer Science · Engineering · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
- A Direct Sum Result for the Information Complexity of Learning
2018/04/16 by Nachum, Ido, Shafer, Jonathan, Yehudayoff, Amir · 1 citation
#FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML)
- The discrepancy of greater-than
2023/09/15 by Srinivasan, Srikanth, Yehudayoff, Amir · 2 citations
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
- On Symmetry and Initialization for Neural Networks
2019/07/01 by Ido Nachum, Nachum, Ido, Amir Yehudayoff +1 · 1 citation
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Neural Networks and Applications #Stochastic Gradient Optimization Techniques
- Dual VC Dimension Obstructs Sample Compression by Embeddings
2024/05/27 by Chase, Zachary, Chornomaz, Bogdan, Hanneke, Steve +2 · 2 citations
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.1 #I.2.6 #Machine Learning (cs.LG)
- Slicing the hypercube is not easy
2021/02/10 by Gal Yehuda, Yehuda, Gal, Amir Yehudayoff +1 · 1 citation
Computer Science · Engineering · #05D05 #52C35 #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Combinatorics (math.CO) #Computational Complexity (cs.CC) #F.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #Interconnection Networks and Systems #graph theory and CDMA systems
- Tight bounds on the Fourier growth of bounded functions on the hypercube
2021/07/13 by Siddharth Iyer, Iyer, Siddharth, Anup Rao +7 · 1 citation
Mathematics · #Advanced Topology and Set Theory #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Limits and Structures in Graph Theory #Meromorphic and Entire Functions
- A lower bound for essential covers of the cube
2021/05/28 by Yehuda, Gal, Yehudayoff, Amir · 1 citation
#05D99 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1
- A Unified Characterization of Private Learnability via Graph Theory
2023/04/08 by Alon, Noga, Moran, Shay, Schefler, Hilla +1 · 2 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG)
- Fixed and Periodic Points of the Intersection Body Operator
2024/08/15 by Emanuel Milman, Milman, Emanuel, Shahar Shabelman +3 · 2 citations
Mathematics · #Algebraic and Geometric Analysis #Differential Equations and Boundary Problems #FOS: Mathematics #Functional Analysis (math.FA) #Metric Geometry (math.MG) #Spectral Theory in Mathematical Physics
- Better Neural Network Expressivity: Subdividing the Simplex
2025/05/20 by Bakaev, Egor, Brunck, Florestan, Hertrich, Christoph +2 · 4 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Neural and Evolutionary Computing (cs.NE)
- Anti-concentration in most directions
2018/11/15 by Anup Rao, Rao, Anup, Amir Yehudayoff +1 · 1 citation
Computer Science · Mathematics · #60C05 #68Q87 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)
- On the Depth of Monotone ReLU Neural Networks and ICNNs
2025/05/09 by Egor Bakaev, Florestan Brunck, Bakaev, Egor +7 · 3 citations
Computer Science · #Stochastic Gradient Optimization Techniques #Advanced Graph Neural Networks #Neural Networks and Applications
- Negations are powerful even in small depth
2025/12/22 by Cavalar, Bruno, Fabris, Théo Borém, Mukhopadhyay, Partha +2 · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences