Amir Yehudayoff

ORCID

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 96

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

COLT

STOC

Publications

Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, Amir Yehudayoff
Dual VC Dimension Obstructs Sample Compression by Embeddings. CoRR (2024)
Gal Yehuda, Amir Yehudayoff
A Lower Bound for Essential Covers of the Cube. Comb. 44 (4) (2024)
Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff
A Unified Characterization of Private Learnability via Graph Theory. COLT (2024)
Daniel Avraham, Amir Yehudayoff
On Blocky Ranks Of Matrices. Comput. Complex. 33 (1) (2024)
Daniel Carmon, Amir Yehudayoff, Roi Livni
The sample complexity of ERMs in stochastic convex optimization. AISTATS (2024)
Zachary Chase, Bogdan Chornomaz, Shay Moran, Amir Yehudayoff
Local Borsuk-Ulam, Stability, and Replicability. STOC (2024)
Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, Amir Yehudayoff
Dual VC Dimension Obstructs Sample Compression by Embeddings. COLT (2024)
Zachary Chase, Bogdan Chornomaz, Shay Moran, Amir Yehudayoff
Local Borsuk-Ulam, Stability, and Replicability. CoRR (2023)
Zachary Chase, Shay Moran, Amir Yehudayoff
Stability and Replicability in Learning. FOCS (2023)
Daniel Carmon, Roi Livni, Amir Yehudayoff
The Sample Complexity Of ERMs In Stochastic Convex Optimization. CoRR (2023)
Zachary Chase, Shay Moran, Amir Yehudayoff
Replicability and stability in learning. CoRR (2023)
Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff
A Unified Characterization of Private Learnability via Graph Theory. CoRR (2023)
Srikanth Srinivasan, Amir Yehudayoff
The discrepancy of greater-than. CoRR (2023)
Benjamin E. Diamond, Amir Yehudayoff
Explicit exponential lower bounds for exact hyperplane covers. Discret. Math. 345 (11) (2022)
Daniel Avraham, Amir Yehudayoff
On blocky ranks of matrices. Electron. Colloquium Comput. Complex. (2022)
Anup Rao, Amir Yehudayoff
Anticoncentration and the Exact Gap-Hamming Problem. SIAM J. Discret. Math. 36 (2) (2022)
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff
A Characterization of Multiclass Learnability. CoRR (2022)
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff
A Characterization of Multiclass Learnability. FOCS (2022)
Zilin Jiang, Amir Yehudayoff
An Isoperimetric Inequality for Hamming Balls and Local Expansion in Hypercubes. Electron. J. Comb. 29 (1) (2022)
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff
A Characterization of Multiclass Learnability. Electron. Colloquium Comput. Complex. (2022)
Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff
Tight bounds on the Fourier growth of bounded functions on the hypercube. Electron. Colloquium Comput. Complex. 28 (2021)
Gal Yehuda, Amir Yehudayoff
A lower bound for essential covers of the cube. CoRR (2021)
Gal Yehuda, Amir Yehudayoff
Slicing the hypercube is not easy. CoRR (2021)
Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff
Interactive Proofs for Verifying Machine Learning. ITCS (2021)
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff
On the Communication Complexity of Key-Agreement Protocols. CoRR (2021)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
Learnability can be independent of set theory (invited paper). STOC (2021)
Pavel Hrubes, Amir Yehudayoff
Shadows of Newton Polytopes. Computational Complexity Conference (2021)
Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff
Tight bounds on the Fourier growth of bounded functions on the hypercube. CoRR (2021)
Elisabetta Cornacchia, Jan Hazla, Ido Nachum, Amir Yehudayoff
Regularization by Misclassification in ReLU Neural Networks. CoRR (2021)
Benjamin Diamond, Amir Yehudayoff
Explicit Exponential Lower Bounds for Exact Hyperplane Covers. Electron. Colloquium Comput. Complex. 28 (2021)
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, Amir Yehudayoff
A theory of universal learning. STOC (2021)
Shay Moran, Ido Nachum, Itai Panasoff, Amir Yehudayoff
On the Perceptron's Compression. CiE (2020)
Amir Yehudayoff
Pointer chasing via triangular discrimination. Comb. Probab. Comput. 29 (4) (2020)
Parikshit Gopalan, Amir Yehudayoff
Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials. Theory Comput. 16 (2020)
Shay Moran, Amir Yehudayoff
On Weak ε-Nets and the Radon Number. Discret. Comput. Geom. 64 (4) (2020)
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, Amir Yehudayoff
A Theory of Universal Learning. CoRR (2020)
Pavel Hrubes, Amir Yehudayoff
Shadows of Newton polytopes. Electron. Colloquium Comput. Complex. 27 (2020)
Ido Nachum, Amir Yehudayoff
On Symmetry and Initialization for Neural Networks. LATIN (2020)
Ofer M. Shir, Amir Yehudayoff
On the covariance-Hessian relation in evolution strategies. Theor. Comput. Sci. 801 (2020)
Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff
Interactive Proofs for Verifying Machine Learning. Electron. Colloquium Comput. Complex. 27 (2020)
Anup Rao, Amir Yehudayoff
The Communication Complexity of the Exact Gap-Hamming Problem. Electron. Colloquium Comput. Complex. 27 (2020)
Amir Yehudayoff
Separating monotone VP and VNP. STOC (2019)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound. Comput. Complex. 28 (1) (2019)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
Learnability can be undecidable. Nat. Mach. Intell. 1 (1) (2019)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
Author Correction: Learnability can be undecidable. Nat. Mach. Intell. 1 (2) (2019)
Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. ICALP (2019)
Ido Nachum, Amir Yehudayoff
Average-Case Information Complexity of Learning. ALT (2019)
Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff
On Communication Complexity of Classification Problems. COLT (2019)
Shay Moran, Amir Yehudayoff
On Weak epsilon-Nets and the Radon Number. SoCG (2019)
Stephan Gocht, Jakob Nordström, Amir Yehudayoff
On Division Versus Saturation in Pseudo-Boolean Solving. IJCAI (2019)
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff
On the Communication Complexity of Key-Agreement Protocols. ITCS (2019)
Ido Nachum, Amir Yehudayoff
On Symmetry and Initialization for Neural Networks. CoRR (2019)
Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. Electron. Colloquium Comput. Complex. 26 (2019)
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff
On the Communication Complexity of Key-Agreement Protocols. Electron. Colloquium Comput. Complex. 25 (2018)
Amir Yehudayoff
Anti-concentration in most directions. Electron. Colloquium Comput. Complex. 25 (2018)
Shay Moran, Ido Nachum, Itai Panasoff, Amir Yehudayoff
On the Perceptron's Compression. CoRR (2018)
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, Amir Yehudayoff
Distributed construction of purely additive spanners. Distributed Comput. 31 (3) (2018)
Ofer M. Shir, Amir Yehudayoff
On the Covariance-Hessian Relation in Evolution Strategies. CoRR (2018)
Amir Yehudayoff
Separating Monotone VP and VNP. Electron. Colloquium Comput. Complex. 25 (2018)
Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, Amir Yehudayoff
Learners that Use Little Information. ALT (2018)
Ido Nachum, Jonathan Shafer, Amir Yehudayoff
A Direct Sum Result for the Information Complexity of Learning. CoRR (2018)
Ido Nachum, Amir Yehudayoff
Average-Case Information Complexity of Learning. CoRR (2018)
Ido Nachum, Jonathan Shafer, Amir Yehudayoff
A Direct Sum Result for the Information Complexity of Learning. COLT (2018)
Daniel M. Kane, Roi Livni, Shay Moran, Amir Yehudayoff
On Communication Complexity of Classification Problems. Electron. Colloquium Comput. Complex. 24 (2017)
Amir Yehudayoff
An Elementary Exposition of Topological Overlap in the Plane. Discret. Comput. Geom. 58 (2) (2017)
Shay Moran, Amir Yehudayoff
On weak $ε$-nets and the Radon number. CoRR (2017)
Ofer M. Shir, Amir Yehudayoff
On the Statistical Learning Ability of Evolution Strategies. FOGA (2017)
Daniel M. Kane, Roi Livni, Shay Moran, Amir Yehudayoff
On Communication Complexity of Classification Problems. CoRR (2017)
Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, Shay Moran, Amir Yehudayoff
Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues. NIPS (2017)
Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, Shay Moran, Amir Yehudayoff
Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues. CoRR (2017)
Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, Amir Yehudayoff
Learners that Leak Little Information. CoRR (2017)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
A learning problem that is independent of the set theory ZFC axioms. CoRR (2017)
Avi Wigderson, Amir Yehudayoff
Population recovery and partial identification. Mach. Learn. 102 (1) (2016)
Noga Alon, Shay Moran, Amir Yehudayoff
Sign rank versus VC dimension. COLT (2016)
Shay Moran, Amir Yehudayoff
A Note on Average-Case Sorting. Order 33 (1) (2016)
Ofer M. Shir, Jonathan Roslund, Amir Yehudayoff
On the Theoretical Capacity of Evolution Strategies to Statistically Learn the Landscape Hessian. CoRR (2016)
Ofir David, Shay Moran, Amir Yehudayoff
On statistical learning via the lens of compression. CoRR (2016)
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, Amir Yehudayoff
Distributed Construction of Purely Additive Spanners. DISC (2016)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Direct Sum Fails for Zero-Error Average Communication. Algorithmica 76 (3) (2016)
Ofer M. Shir, Jonathan Roslund, Amir Yehudayoff
On the Capacity of Evolution Strategies to Statistically Learn the Landscape. GECCO (Companion) (2016)
Shay Moran, Makrand Sinha, Amir Yehudayoff
Fooling Pairs in Randomized Communication Complexity. SIROCCO (2016)
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, Amir Yehudayoff
Distributed Construction of Purely Additive Spanners. CoRR (2016)
Shay Moran, Amir Yehudayoff
Sample compression schemes for VC classes. ITA (2016)
Ofir David, Shay Moran, Amir Yehudayoff
Supervised learning through the lens of compression. NIPS (2016)
Shay Moran, Amir Yehudayoff
Sample Compression Schemes for VC Classes. J. ACM 63 (3) (2016)
Pavel Hrubes, Amir Yehudayoff
On Isoperimetric Profiles and Computational Complexity. ICALP (2016)
Amir Yehudayoff
Pointer chasing via triangular discrimination. Electron. Colloquium Comput. Complex. 23 (2016)
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
Teaching and compressing for low VC-dimension. CoRR (2015)
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
Teaching and compressing for low VC-dimension. Electron. Colloquium Comput. Complex. 22 (2015)
Shay Moran, Amir Yehudayoff
Proper PAC learning is compressing. CoRR (2015)
Pavel Hrubes, Amir Yehudayoff
On isoperimetric profiles and computational complexity. Electron. Colloquium Comput. Complex. 22 (2015)
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
Compressing and Teaching for Low VC-Dimension. FOCS (2015)
Balthazar Bauer, Shay Moran, Amir Yehudayoff
Internal Compression of Protocols to Entropy. APPROX-RANDOM (2015)
Shay Moran, Amir Yehudayoff
Proper PAC learning is compressing. Electron. Colloquium Comput. Complex. 22 (2015)
Anup Rao, Amir Yehudayoff
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness. Computational Complexity Conference (2015)
David Ellis, Ehud Friedgut, Guy Kindler, Amir Yehudayoff
Geometric stability via information theory. CoRR (2015)
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
Pseudorandom Generators for Regular Branching Programs. SIAM J. Comput. 43 (3) (2014)
Shay Moran, Makrand Sinha, Amir Yehudayoff
Fooling Pairs in Randomized Communication Complexity. Electron. Colloquium Comput. Complex. 21 (2014)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound. ICALP (1) (2014)
Balthazar Bauer, Shay Moran, Amir Yehudayoff
Internal compression of protocols to entropy. Electron. Colloquium Comput. Complex. 21 (2014)

Amir Yehudayoff.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Amir Yehudayoff