Tali Kaufman

According to our database, Tali Kaufman authored at least 86 papers between 2003 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes.

Uriya A. First, Tali Kaufman

CoRR, 2024

2023

High dimensional expanders and coset geometries.

Tali Kaufman, Izhar Oppenheim

Eur. J. Comb., June, 2023

NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes.

Louis Golowich, Tali Kaufman

Electron. Colloquium Comput. Complex., 2023

No Where to Go But High: A Perspective on High Dimensional Expanders.

Roy Gotlib, Tali Kaufman

CoRR, 2023

Garland's Technique for Posets and High Dimensional Grassmannian Expanders.

Tali Kaufman, Ran J. Tessler

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

List Agreement Expansion from Coboundary Expansion.

Roy Gotlib, Tali Kaufman

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Fine Grained Analysis of High Dimensional Random Walks.

Roy Gotlib, Tali Kaufman

Proceedings of the Approximation, 2023

2022

From Local to Robust Testing via Agreement Testing.

Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi

Theory Comput., 2022

Beyond the Worst Case: Structured Convergence of High Dimensional Random Walks.

Roy Gotlib, Tali Kaufman

CoRR, 2022

On Good 2-Query Locally Testable Codes from Sheaves on High Dimensional Expanders.

Uriya A. First, Tali Kaufman

CoRR, 2022

Couboundary Expansion of Sheaves on Graphs and Weighted Mixing Lemmas.

Uriya A. First, Tali Kaufman

CoRR, 2022

Combinatorics via closed orbits: number theoretic Ramanujan graphs are not unique neighbor expanders.

Amitay Kamber, Tali Kaufman

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Hypercontractivity on high dimensional expanders.

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Scalar and Matrix Chernoff Bounds from ℓ_∞-Independence.

Tali Kaufman, Rasmus Kyng, Federico Soldà

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games.

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Improved Optimal Testing Results from Global Hypercontractivity.

Tali Kaufman, Dor Minzer

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

High Dimensional Expansion Implies Amplified Local Testability.

Tali Kaufman, Izhar Oppenheim

Proceedings of the Approximation, 2022

Double Balanced Sets in High Dimensional Expanders.

Tali Kaufman, David Mass

Proceedings of the Approximation, 2022

Eigenstripping, Spectral Decay, and Edge-Expansion on Posets.

Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang

Proceedings of the Approximation, 2022

2021

Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments.

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Electron. Colloquium Comput. Complex., 2021

Local to global high dimensional expansion and Garland's method for general posets.

Tali Kaufman, Ran J. Tessler

CoRR, 2021

Erratum to: High Order Random Walks: Beyond Spectral Gap.

Tali Kaufman, Izhar Oppenheim

Comb., 2021

New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω(√<i>n</i> log^<i>k</i> <i>n</i>) distance.

Tali Kaufman, Ran J. Tessler

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion.

Tali Kaufman, David Mass

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Coboundary and Cosystolic Expansion from Strong Symmetry.

Tali Kaufman, Izhar Oppenheim

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games.

Max Hopkins, Tali Kaufman, Shachar Lovett

Electron. Colloquium Comput. Complex., 2020

Quantum LDPC codes with Ω(√n log^kn) distance, for any k.

Tali Kaufman, Ran J. Tessler

CoRR, 2020

Decodable quantum LDPC codes beyond the √n distance barrier using high dimensional expanders.

Shai Evra, Tali Kaufman, Gilles Zémor

CoRR, 2020

High Order Random Walks: Beyond Spectral Gap.

Tali Kaufman, Izhar Oppenheim

Comb., 2020

Local-To-Global Agreement Expansion via the Variance Method.

Tali Kaufman, David Mass

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders.

Shai Evra, Tali Kaufman, Gilles Zémor

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Chernoff Bound for High-Dimensional Expanders.

Tali Kaufman, Ella Sharakanski

Proceedings of the Approximation, 2020

2019

Testing Odd Direct Sums Using High Dimensional Expanders.

Roy Gotlib, Tali Kaufman

Electron. Colloquium Comput. Complex., 2019

2018

Cosystolic Expanders over any Abelian Group.

Tali Kaufman, David Mass

Electron. Colloquium Comput. Complex., 2018

From Local to Robust Testing via Agreement Testing.

Irit Dinur, Tali Kaufman, Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2018

List Decoding with Double Samplers.

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2018

Good Distance Lattices from High Dimensional Expanders.

Tali Kaufman, David Mass

CoRR, 2018

Construction of new local spectral high dimensional expanders.

Tali Kaufman, Izhar Oppenheim

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

High dimensional expanders imply agreement expanders.

Irit Dinur, Tali Kaufman

Electron. Colloquium Comput. Complex., 2017

High Dimensional Random Walks and Colorful Expansion.

Tali Kaufman, David Mass

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

Walking on the Edge and Cosystolic Expansion.

Tali Kaufman, David Mass

CoRR, 2016

High Dimensional Combinatorial Random Walks and Colorful Expansion.

Tali Kaufman, David Mass

CoRR, 2016

Symmetric LDPC codes and local testing.

Tali Kaufman, Avi Wigderson

Comb., 2016

Bounded degree cosystolic expanders of every dimension.

Shai Evra, Tali Kaufman

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

On Expansion and Topological Overlap.

Dominic Dotterrer, Tali Kaufman, Uli Wagner

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Systolic Expanders of Every Dimension.

Shai Evra, Tali Kaufman

CoRR, 2015

2014

Isoperimetric Inequalities for Ramanujan Complexes and Topological Expanders.

Tali Kaufman, David Kazhdan, Alexander Lubotzky

CoRR, 2014

High dimensional expanders and property testing.

Tali Kaufman, Alexander Lubotzky

Proceedings of the Innovations in Theoretical Computer Science, 2014

Ramanujan Complexes and Bounded Degree Topological Expanders.

Tali Kaufman, David Kazhdan, Alexander Lubotzky

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

2-Transitivity is Insufficient for Local Testability.

Elena Grigorescu, Tali Kaufman, Madhu Sudan

Comput. Complex., 2013

Comparing the strength of query types in property testing: The case of k-colorability.

Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron

Comput. Complex., 2013

2012

Weight Distribution and List-Decoding Size of Reed-Muller Codes.

Tali Kaufman, Shachar Lovett, Ely Porat

IEEE Trans. Inf. Theory, 2012

Explicit Low-Weight Bases for BCH Codes.

Elena Grigorescu, Tali Kaufman

IEEE Trans. Inf. Theory, 2012

Succinct Representation of Codes with Applications to Testing.

Elena Grigorescu, Tali Kaufman, Madhu Sudan

SIAM J. Discret. Math., 2012

Edge transitive ramanujan graphs and symmetric LDPC good codes.

Tali Kaufman, Alexander Lubotzky

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Dense locally testable codes cannot have constant rate and distance.

Irit Dinur, Tali Kaufman

Electron. Colloquium Comput. Complex., 2011

Edge Transitive Ramanujan Graphs and Highly Symmetric LDPC Good Codes

Tali Kaufman, Alexander Lubotzky

CoRR, 2011

New Extension of the Weil Bound for Character Sums with Applications to Coding.

Tali Kaufman, Shachar Lovett

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Proximity Oblivious Testing and the Role of Invariances.

Oded Goldreich, Tali Kaufman

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010

Breaking the Epsilon-Soundness Bound of the Linearity Test over GF(2).

Tali Kaufman, Simon Litsyn, Ning Xie

SIAM J. Comput., 2010

Locally Testable vs. Locally Decodable Codes.

Tali Kaufman, Michael Viderman

Electron. Colloquium Comput. Complex., 2010

Testing of exponentially large codes, by a new extension to Weil bound for character sums.

Tali Kaufman, Shachar Lovett

Electron. Colloquium Comput. Complex., 2010

Proximity Oblivious Testing and the Role of Invariances.

Oded Goldreich, Tali Kaufman

Electron. Colloquium Comput. Complex., 2010

Symmetric LDPC Codes and Local Testing.

Tali Kaufman, Avi Wigderson

Proceedings of the Property Testing - Current Research and Surveys, 2010

Comparing the Strength of Query Types in Property Testing: The Case of Testing <i>k</i>-Colorability.

Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron

Proceedings of the Property Testing - Current Research and Surveys, 2010

Local computation in codes.

Tali Kaufman

Proceedings of the 2010 IEEE Information Theory Workshop, 2010

2009

Locally Testable Codes Require Redundant Testers.

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Electron. Colloquium Comput. Complex., 2009

2008

Testing Triangle-Freeness in General Graphs.

Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron

SIAM J. Discret. Math., 2008

The List-Decoding Size of Reed-Muller Codes.

Shachar Lovett, Tali Kaufman

Electron. Colloquium Comput. Complex., 2008

Worst case to Average case reductions for polynomials.

Shachar Lovett, Tali Kaufman

Electron. Colloquium Comput. Complex., 2008

Comparing the strength of query types in property testing: the case of testing <i>k</i>-colorability.

Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007

Guessing secrets efficiently via list decoding.

Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan

ACM Trans. Algorithms, 2007

Algebraic Property Testing: The Role of Invariance.

Tali Kaufman, Madhu Sudan

Electron. Colloquium Comput. Complex., 2007

Sparse Random Linear Codes are Locally Decodable and Testable.

Tali Kaufman, Madhu Sudan

Electron. Colloquium Comput. Complex., 2007

Breaking the ε-Soundness Bound of the Linearity Test over GF(2).

Tali Kaufman, Simon Litsyn, Ning Xie

Electron. Colloquium Comput. Complex., 2007

A (De)constructive Approach to Program Checking.

Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum

Electron. Colloquium Comput. Complex., 2007

Verifying and decoding in constant depth.

Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Testing k-wise and almost k-wise independence.

Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Testing Polynomials over General Fields.

Tali Kaufman, Dana Ron

SIAM J. Comput., 2006

Long Extended BCH Codes Are Spanned by Minimum Weight Words.

Tali Kaufman, Simon Litsyn

Proceedings of the Applied Algebra, 2006

2005

Property testing of graphs and codes

Tali Kaufman

PhD thesis, 2005

A characterization of low-weight words that span generalized reed-muller codes.

Tali Kaufman, Dana Ron

IEEE Trans. Inf. Theory, 2005

Testing Reed-Muller codes.

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron

IEEE Trans. Inf. Theory, 2005

Almost Orthogonal Linear Codes are Locally Testable.

Tali Kaufman, Simon Litsyn

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Tight Bounds for Testing Bipartiteness in General Graphs.

Tali Kaufman, Michael Krivelevich, Dana Ron

SIAM J. Comput., 2004

2003

Testing Low-Degree Polynomials over GF(2(.

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron

Proceedings of the Approximation, 2003