Amir Yehudayoff

171 papers A* 28A 12B 4C 1Misc 1Journal 118Unranked 7
YearRankTypeTitle / Venue / Authors
2026 J jnl
A LYM inequality for product measures.
Discret. Math.
Gal Yehuda, Amir Yehudayoff
2026 J jnl
Multilinear Algebraic Branching Programs and the Min-Partition Rank Method.
Electron. Colloquium Comput. Complex.
Théo Borém Fabris, Nutan Limaye, Srikanth Srinivasan, Amir Yehudayoff
2025 J jnl
Approximation Depth of Convex Polytopes.
CoRR
Egor Bakaev, Florestan Brunck, Amir Yehudayoff
2025 J jnl
Better Neural Network Expressivity: Subdividing the Simplex.
CoRR
Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, Amir Yehudayoff
2025 A* conf
Data Selection for ERMs.
COLT
Steve Hanneke, Shay Moran, Alexander Shlimovich, Amir Yehudayoff
2025 J jnl
Data Selection for ERMs.
CoRR
Steve Hanneke, Shay Moran, Alexander Shlimovich, Amir Yehudayoff
2025 J jnl
Negations are powerful even in small depth.
CoRR
Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff
2025 J jnl
Negations are powerful even in small depth.
Electron. Colloquium Comput. Complex.
Bruno Pasqualotto Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff
2025 J jnl
On the Depth of Monotone ReLU Neural Networks and ICNNs.
CoRR
Egor Bakaev, Florestan Brunck, Christoph Hertrich, Daniel Reichman, Amir Yehudayoff
2025 J jnl
On the Space Complexity of Online Convolution.
CoRR
Joel Daniel Andersson, Amir Yehudayoff
2025 A* conf
Open Problem: Data Selection for Regression Tasks.
COLT
Steve Hanneke, Shay Moran, Alexander Shlimovich, Amir Yehudayoff
2025 — conf
The Algebraic Cost of a Boolean Sum.
FSTTCS
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff
2025 J jnl
The Algebraic Cost of a Boolean Sum.
CoRR
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff
2025 J jnl
The Algebraic Cost of a Boolean Sum.
Electron. Colloquium Comput. Complex.
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff
2024 J jnl
A Lower Bound for Essential Covers of the Cube.
Comb.
Gal Yehuda, Amir Yehudayoff
2024 A* conf
A Unified Characterization of Private Learnability via Graph Theory.
COLT
Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff
2024 A* conf
Dual VC Dimension Obstructs Sample Compression by Embeddings.
COLT
Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, Amir Yehudayoff
2024 J jnl
Dual VC Dimension Obstructs Sample Compression by Embeddings.
CoRR
Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, Amir Yehudayoff
2024 A* conf
Local Borsuk-Ulam, Stability, and Replicability.
STOC
Zachary Chase, Bogdan Chornomaz, Shay Moran, Amir Yehudayoff
2024 J jnl
On Blocky Ranks Of Matrices.
Comput. Complex.
Daniel Avraham, Amir Yehudayoff
2024 A conf
The sample complexity of ERMs in stochastic convex optimization.
AISTATS
Daniel Carmon, Amir Yehudayoff, Roi Livni
2023 J jnl
A Unified Characterization of Private Learnability via Graph Theory.
CoRR
Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff
2023 J jnl
Local Borsuk-Ulam, Stability, and Replicability.
CoRR
Zachary Chase, Bogdan Chornomaz, Shay Moran, Amir Yehudayoff
2023 J jnl
Replicability and stability in learning.
CoRR
Zachary Chase, Shay Moran, Amir Yehudayoff
2023 A* conf
Stability and Replicability in Learning.
FOCS
Zachary Chase, Shay Moran, Amir Yehudayoff
2023 J jnl
The Sample Complexity Of ERMs In Stochastic Convex Optimization.
CoRR
Daniel Carmon, Roi Livni, Amir Yehudayoff
2023 J jnl
The discrepancy of greater-than.
CoRR
Srikanth Srinivasan, Amir Yehudayoff
2022 A* conf
A Characterization of Multiclass Learnability.
FOCS
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff
2022 J jnl
A Characterization of Multiclass Learnability.
CoRR
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff
2022 J jnl
A Characterization of Multiclass Learnability.
Electron. Colloquium Comput. Complex.
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff
2022 J jnl
An Isoperimetric Inequality for Hamming Balls and Local Expansion in Hypercubes.
Electron. J. Comb.
Zilin Jiang, Amir Yehudayoff
2022 J jnl
Anticoncentration and the Exact Gap-Hamming Problem.
SIAM J. Discret. Math.
Anup Rao, Amir Yehudayoff
2022 J jnl
Explicit exponential lower bounds for exact hyperplane covers.
Discret. Math.
Benjamin E. Diamond, Amir Yehudayoff
2022 J jnl
On blocky ranks of matrices.
Electron. Colloquium Comput. Complex.
Daniel Avraham, Amir Yehudayoff
2021 J jnl
A lower bound for essential covers of the cube.
CoRR
Gal Yehuda, Amir Yehudayoff
2021 A* conf
A theory of universal learning.
STOC
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, Amir Yehudayoff
2021 J jnl
Explicit Exponential Lower Bounds for Exact Hyperplane Covers.
Electron. Colloquium Comput. Complex.
Benjamin E. Diamond, Amir Yehudayoff
2021 A conf
Interactive Proofs for Verifying Machine Learning.
ITCS
Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff
2021 A* conf
Learnability can be independent of set theory (invited paper).
STOC
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
2021 J jnl
On the Communication Complexity of Key-Agreement Protocols.
CoRR
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff
2021 J jnl
Regularization by Misclassification in ReLU Neural Networks.
CoRR
Elisabetta Cornacchia, Jan Hazla, Ido Nachum, Amir Yehudayoff
2021 A conf
Shadows of Newton Polytopes.
CCC
Pavel Hrubes, Amir Yehudayoff
2021 J jnl
Slicing the hypercube is not easy.
CoRR
Gal Yehuda, Amir Yehudayoff
2021 J jnl
Tight bounds on the Fourier growth of bounded functions on the hypercube.
CoRR
Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff
2021 J jnl
Tight bounds on the Fourier growth of bounded functions on the hypercube.
Electron. Colloquium Comput. Complex.
Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff
2020 J jnl
A Theory of Universal Learning.
CoRR
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, Amir Yehudayoff
2020 J jnl
Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials.
Theory Comput.
Parikshit Gopalan, Amir Yehudayoff
2020 J jnl
Interactive Proofs for Verifying Machine Learning.
Electron. Colloquium Comput. Complex.
Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff
2020 B conf
On Symmetry and Initialization for Neural Networks.
LATIN
Ido Nachum, Amir Yehudayoff
2020 J jnl
On Weak ε-Nets and the Radon Number.
Discret. Comput. Geom.
Shay Moran, Amir Yehudayoff
2020 C conf
On the Perceptron's Compression.
CiE
Shay Moran, Ido Nachum, Itai Panasoff, Amir Yehudayoff
2020 J jnl
On the covariance-Hessian relation in evolution strategies.
Theor. Comput. Sci.
Ofer M. Shir, Amir Yehudayoff
2020 J jnl
Pointer chasing via triangular discrimination.
Comb. Probab. Comput.
Amir Yehudayoff
2020 J jnl
Shadows of Newton polytopes.
Electron. Colloquium Comput. Complex.
Pavel Hrubes, Amir Yehudayoff
2020 J jnl
The Communication Complexity of the Exact Gap-Hamming Problem.
Electron. Colloquium Comput. Complex.
Anup Rao, Amir Yehudayoff
2019 J jnl
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound.
Comput. Complex.
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2019 J jnl
Author Correction: Learnability can be undecidable.
Nat. Mach. Intell.
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
2019 B conf
Average-Case Information Complexity of Learning.
ALT
Ido Nachum, Amir Yehudayoff
2019 J jnl
Learnability can be undecidable.
Nat. Mach. Intell.
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
2019 A* conf
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits.
ICALP
Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff
2019 J jnl
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits.
Electron. Colloquium Comput. Complex.
Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff
2019 A* conf
On Communication Complexity of Classification Problems.
COLT
Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff
2019 A* conf
On Division Versus Saturation in Pseudo-Boolean Solving.
IJCAI
Stephan Gocht, Jakob Nordström, Amir Yehudayoff
2019 J jnl
On Symmetry and Initialization for Neural Networks.
CoRR
Ido Nachum, Amir Yehudayoff
2019 A* conf
On Weak epsilon-Nets and the Radon Number.
SoCG
Shay Moran, Amir Yehudayoff
2019 A conf
On the Communication Complexity of Key-Agreement Protocols.
ITCS
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff
2019 A* conf
Separating monotone VP and VNP.
STOC
Amir Yehudayoff
2018 A* conf
A Direct Sum Result for the Information Complexity of Learning.
COLT
Ido Nachum, Jonathan Shafer, Amir Yehudayoff
2018 J jnl
A Direct Sum Result for the Information Complexity of Learning.
CoRR
Ido Nachum, Jonathan Shafer, Amir Yehudayoff
2018 J jnl
Anti-concentration in most directions.
Electron. Colloquium Comput. Complex.
Amir Yehudayoff
2018 J jnl
Average-Case Information Complexity of Learning.
CoRR
Ido Nachum, Amir Yehudayoff
2018 J jnl
Distributed construction of purely additive spanners.
Distributed Comput.
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, Amir Yehudayoff
2018 B conf
Learners that Use Little Information.
ALT
Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, Amir Yehudayoff
2018 J jnl
On the Communication Complexity of Key-Agreement Protocols.
Electron. Colloquium Comput. Complex.
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff
2018 J jnl
On the Covariance-Hessian Relation in Evolution Strategies.
CoRR
Ofer M. Shir, Amir Yehudayoff
2018 J jnl
On the Perceptron's Compression.
CoRR
Shay Moran, Ido Nachum, Itai Panasoff, Amir Yehudayoff
2018 J jnl
Separating Monotone VP and VNP.
Electron. Colloquium Comput. Complex.
Amir Yehudayoff
2017 J jnl
A learning problem that is independent of the set theory ZFC axioms.
CoRR
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
2017 J jnl
An Elementary Exposition of Topological Overlap in the Plane.
Discret. Comput. Geom.
Amir Yehudayoff
2017 J jnl
Learners that Leak Little Information.
CoRR
Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, Amir Yehudayoff
2017 J jnl
On Communication Complexity of Classification Problems.
CoRR
Daniel M. Kane, Roi Livni, Shay Moran, Amir Yehudayoff
2017 J jnl
On Communication Complexity of Classification Problems.
Electron. Colloquium Comput. Complex.
Daniel M. Kane, Roi Livni, Shay Moran, Amir Yehudayoff
2017 A conf
On the Statistical Learning Ability of Evolution Strategies.
FOGA
Ofer M. Shir, Amir Yehudayoff
2017 J jnl
On weak $ε$-nets and the Radon number.
CoRR
Shay Moran, Amir Yehudayoff
2017 — conf
Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues.
NIPS
Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, Shay Moran, Amir Yehudayoff
2017 J jnl
Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues.
CoRR
Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, Shay Moran, Amir Yehudayoff
2016 J jnl
A Note on Average-Case Sorting.
Order
Shay Moran, Amir Yehudayoff
2016 J jnl
Direct Sum Fails for Zero-Error Average Communication.
Algorithmica
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2016 A conf
Distributed Construction of Purely Additive Spanners.
DISC
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, Amir Yehudayoff
2016 J jnl
Distributed Construction of Purely Additive Spanners.
CoRR
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, Amir Yehudayoff
2016 B conf
Fooling Pairs in Randomized Communication Complexity.
SIROCCO
Shay Moran, Makrand Sinha, Amir Yehudayoff
2016 A* conf
On Isoperimetric Profiles and Computational Complexity.
ICALP
Pavel Hrubes, Amir Yehudayoff
2016 J jnl
On statistical learning via the lens of compression.
CoRR
Ofir David, Shay Moran, Amir Yehudayoff
2016 — conf
On the Capacity of Evolution Strategies to Statistically Learn the Landscape.
GECCO (Companion)
Ofer M. Shir, Jonathan Roslund, Amir Yehudayoff
2016 J jnl
On the Theoretical Capacity of Evolution Strategies to Statistically Learn the Landscape Hessian.
CoRR
Ofer M. Shir, Jonathan Roslund, Amir Yehudayoff
2016 J jnl
Pointer chasing via triangular discrimination.
Electron. Colloquium Comput. Complex.
Amir Yehudayoff
2016 J jnl
Population recovery and partial identification.
Mach. Learn.
Avi Wigderson, Amir Yehudayoff
2016 J jnl
Sample Compression Schemes for VC Classes.
J. ACM
Shay Moran, Amir Yehudayoff
2016 Misc conf
Sample compression schemes for VC classes.
ITA
Shay Moran, Amir Yehudayoff
2016 A* conf
Sign rank versus VC dimension.
COLT
Noga Alon, Shay Moran, Amir Yehudayoff
2016 — conf
Supervised learning through the lens of compression.
NIPS
Ofir David, Shay Moran, Amir Yehudayoff
2015 A* conf
Compressing and Teaching for Low VC-Dimension.
FOCS
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
2015 J jnl
Geometric stability via information theory.
CoRR
David Ellis, Ehud Friedgut, Guy Kindler, Amir Yehudayoff
2015 — conf
Internal Compression of Protocols to Entropy.
APPROX-RANDOM
Balthazar Bauer, Shay Moran, Amir Yehudayoff
2015 J jnl
On isoperimetric profiles and computational complexity.
Electron. Colloquium Comput. Complex.
Pavel Hrubes, Amir Yehudayoff
2015 J jnl
Proper PAC learning is compressing.
CoRR
Shay Moran, Amir Yehudayoff
2015 J jnl
Proper PAC learning is compressing.
Electron. Colloquium Comput. Complex.
Shay Moran, Amir Yehudayoff
2015 A conf
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness.
CCC
Anup Rao, Amir Yehudayoff
2015 J jnl
Teaching and compressing for low VC-dimension.
CoRR
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
2015 J jnl
Teaching and compressing for low VC-dimension.
Electron. Colloquium Comput. Complex.
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
2014 — conf
Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound.
ICALP (1)
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2014 J jnl
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound.
Electron. Colloquium Comput. Complex.
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2014 A conf
Direct sum fails for zero error average communication.
ITCS
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2014 J jnl
Fooling Pairs in Randomized Communication Complexity.
Electron. Colloquium Comput. Complex.
Shay Moran, Makrand Sinha, Amir Yehudayoff
2014 J jnl
Inequalities and tail bounds for elementary symmetric polynomial.
CoRR
Parikshit Gopalan, Amir Yehudayoff
2014 J jnl
Inequalities and tail bounds for elementary symmetric polynomials.
Electron. Colloquium Comput. Complex.
Parikshit Gopalan, Amir Yehudayoff
2014 J jnl
Internal compression of protocols to entropy.
Electron. Colloquium Comput. Complex.
Balthazar Bauer, Shay Moran, Amir Yehudayoff
2014 J jnl
Pseudorandom Generators for Regular Branching Programs.
SIAM J. Comput.
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
2014 J jnl
Sign rank, VC dimension and spectral gaps.
Electron. Colloquium Comput. Complex.
Noga Alon, Shay Moran, Amir Yehudayoff
2014 J jnl
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness.
Electron. Colloquium Comput. Complex.
Anup Rao, Amir Yehudayoff
2013 J jnl
A note on average-case sorting.
Electron. Colloquium Comput. Complex.
Shay Moran, Amir Yehudayoff
2013 — conf
Direct Product via Round-Preserving Compression.
ICALP (1)
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013 A* conf
Direct Products in Communication Complexity.
FOCS
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013 J jnl
Direct Sum Fails for Zero Error Average Communication.
Electron. Colloquium Comput. Complex.
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff
2013 J jnl
Direct product via round-preserving compression.
Electron. Colloquium Comput. Complex.
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013 A conf
Formulas are Exponentially Stronger than Monotone Circuits in Non-commutative Setting.
CCC
Pavel Hrubes, Amir Yehudayoff
2013 J jnl
Lipschitz Functions on Expanders are Typically Flat.
Comb. Probab. Comput.
Ron Peled, Wojciech Samotij, Amir Yehudayoff
2013 J jnl
Pseudorandomness for Width-2 Branching Programs.
Theory Comput.
Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff
2012 J jnl
Direct Products in Communication Complexity.
Electron. Colloquium Comput. Complex.
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2012 J jnl
Formulas are exponentially stronger than monotone circuits in non-commutative setting.
Electron. Colloquium Comput. Complex.
Pavel Hrubes, Amir Yehudayoff
2012 J jnl
Linear cover time for trees is exponentially unlikely.
Chic. J. Theor. Comput. Sci.
Amir Yehudayoff
2012 A* conf
Monotone expansion.
STOC
Jean Bourgain, Amir Yehudayoff
2012 A* conf
Population Recovery and Partial Identification.
FOCS
Avi Wigderson, Amir Yehudayoff
2012 J jnl
Population Recovery and Partial Identification.
Electron. Colloquium Comput. Complex.
Avi Wigderson, Amir Yehudayoff
2012 J jnl
Proving expansion in three steps.
SIGACT News
Amir Yehudayoff
2012 A conf
Restriction access.
ITCS
Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff
2012 A* conf
Separating multilinear branching programs and formulas.
STOC
Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff
2011 J jnl
Affine extractors over prime fields.
Comb.
Amir Yehudayoff
2011 J jnl
Arithmetic Complexity in Ring Extensions.
Theory Comput.
Pavel Hrubes, Amir Yehudayoff
2011 J jnl
Homogeneous Formulas and Symmetric Polynomials.
Comput. Complex.
Pavel Hrubes, Amir Yehudayoff
2011 J jnl
Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors.
J. Comput. Syst. Sci.
Ran Raz, Amir Yehudayoff
2011 A* conf
Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes.
STOC
Boaz Barak, Zeev Dvir, Amir Yehudayoff, Avi Wigderson
2011 J jnl
Restriction Access.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff
2011 J jnl
Separating multilinear branching programs and formulas.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff
2011 J jnl
The maximal probability that
Random Struct. Algorithms
Ron Peled, Ariel Yadin, Amir Yehudayoff
2010 J jnl
Arithmetic Circuits: A survey of recent results and open questions.
Found. Trends Theor. Comput. Sci.
Amir Shpilka, Amir Yehudayoff
2010 A* conf
Non-commutative circuits and the sum-of-squares problem.
STOC
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
2010 J jnl
Non-commutative circuits and the sum-of-squares problem.
Electron. Colloquium Comput. Complex.
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
2010 A* conf
Pseudorandom Generators for Regular Branching Programs.
FOCS
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
2010 J jnl
Pseudorandom Generators for Regular Branching Programs.
Electron. Colloquium Comput. Complex.
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
2010 J jnl
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes
CoRR
Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff
2010 J jnl
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes.
Electron. Colloquium Comput. Complex.
Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff
2010 A conf
Relationless Completeness and Separations.
CCC
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
2010 J jnl
Relationless completeness and separations.
Electron. Colloquium Comput. Complex.
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
2009 J jnl
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits.
SIAM J. Comput.
Zeev Dvir, Amir Shpilka, Amir Yehudayoff
2009 J jnl
Homogeneous formulas and symmetric polynomials
CoRR
Pavel Hrubes, Amir Yehudayoff
2009 J jnl
Lower Bounds and Separations for Constant Depth Multilinear Circuits.
Comput. Complex.
Ran Raz, Amir Yehudayoff
2009 J jnl
Monotone separations for constant degree polynomials.
Inf. Process. Lett.
Pavel Hrubes, Amir Yehudayoff
2009 J jnl
Players' Effects Under Limited Independence.
Math. Oper. Res.
Ronen Gradwohl, Omer Reingold, Ariel Yadin, Amir Yehudayoff
2009 J jnl
Pseudorandomness for Width 2 Branching Programs.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff
2008 J jnl
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
SIAM J. Comput.
Ran Raz, Amir Shpilka, Amir Yehudayoff
2008 J jnl
Balancing Syntactically Multilinear Arithmetic Circuits.
Comput. Complex.
Ran Raz, Amir Yehudayoff
2008 A* conf
Hardness-randomness tradeoffs for bounded depth arithmetic circuits.
STOC
Zeev Dvir, Amir Shpilka, Amir Yehudayoff
2008 A conf
Lower Bounds and Separations for Constant Depth Multilinear Circuits.
CCC
Ran Raz, Amir Yehudayoff
2008 J jnl
Lower Bounds and Separations for Constant Depth Multilinear Circuits.
Electron. Colloquium Comput. Complex.
Ran Raz, Amir Yehudayoff
2008 A* conf
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.
FOCS
Ran Raz, Amir Yehudayoff
2008 J jnl
t-Wise independence with local dependencies.
Inf. Process. Lett.
Ronen Gradwohl, Amir Yehudayoff
2007 A* conf
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
FOCS
Ran Raz, Amir Shpilka, Amir Yehudayoff
2007 J jnl
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Amir Shpilka, Amir Yehudayoff
2007 J jnl
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.
Electron. Colloquium Comput. Complex.
Ran Raz, Amir Yehudayoff
2006 J jnl
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
Electron. Colloquium Comput. Complex.
Ran Raz, Amir Shpilka, Amir Yehudayoff