Prof. Tali Kaufman

Prof.
Prof. Tali Kaufman
Telephone: 
Fax: 
Email: 
Office: 
Reception hours: 

Publications

Tali Kaufman, Alexander Lubotzky: Edge transitive ramanujan graphs and symmetric LDPC good codes. STOC 2012: 359-366

Elena Grigorescu, Tali Kaufman: Explicit Low-Weight Bases for BCH Codes. IEEE Transactions on Information Theory 58(1): 78-81 (2012)

Tali Kaufman, Shachar LovettEly Porat: Weight Distribution and List-Decoding Size of Reed-Muller Codes. IEEE Transactions on Information Theory 58(5): 2689-2696 (2012)

Irit Dinur, Tali Kaufman: Dense Locally Testable Codes Cannot Have Constant Rate and Distance. APPROX-RANDOM 2011: 507-518

Oded Goldreich, Tali Kaufman: Proximity Oblivious Testing and the Role of Invariances. APPROX-RANDOM 2011: 579-592

Tali Kaufman, Shachar Lovett: New Extension of the Weil Bound for Character Sums with Applications to Coding. FOCS 2011: 788-796

Oded Goldreich, Tali Kaufman: Proximity Oblivious Testing and the Role of Invariances. Studies in Complexity and Cryptography 2011: 173-190

Tali Kaufman, Michael Viderman: Locally Testable vs. Locally Decodable Codes. APPROX-RANDOM 2010: 670-682

Tali Kaufman, Avi Wigderson: Symmetric LDPC Codes and Local Testing. ICS 2010: 406-421

Tali Kaufman, Shachar LovettEly Porat: Weight Distribution and List-Decoding Size of Reed-Muller Codes. ICS 2010: 422-433

Ido Ben-Eliezer, Tali Kaufman, Michael KrivelevichDana Ron: Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability. Property Testing 2010: 253-259

Tali Kaufman, Avi Wigderson: Symmetric LDPC Codes and Local Testing. Property Testing 2010: 312-319

Tali Kaufman, Simon LitsynNing Xie: Breaking the Epsilon-Soundness Bound of the Linearity Test over GF(2). SIAM J. Comput. 39(5): 1988-2003 (2010)

Eli Ben-SassonVenkatesan Guruswami, Tali Kaufman, Madhu SudanMichael Viderman: Locally Testable Codes Require Redundant Testers. SIAM J. Comput. 39(7): 3230-3247 (2010)

Elena Grigorescu, Tali Kaufman, Madhu Sudan: Succinct Representation of Codes with Applications to Testing. APPROX-RANDOM 2009: 534-547

Eli Ben-SassonVenkatesan Guruswami, Tali Kaufman, Madhu SudanMichael Viderman: Locally Testable Codes Require Redundant Testers. IEEE Conference on Computational Complexity 2009: 52-61

Tali Kaufman, Simon LitsynNing Xie: Breaking the epsilon-Soundness Bound of the Linearity Test over GF(2). APPROX-RANDOM 2008: 498-511

Tali Kaufman, Shachar Lovett: Worst Case to Average Case Reductions for Polynomials. FOCS 2008: 166-175

Elena Grigorescu, Tali Kaufman, Madhu Sudan: 2-Transitivity Is Insufficient for Local Testability. IEEE Conference on Computational Complexity 2008: 259-267

Ido Ben-Eliezer, Tali Kaufman, Michael KrivelevichDana Ron: Comparing the strength of query types in property testing: the case of testing k-colorability. SODA 2008: 1213-1222

Shafi GoldwasserDan GutfreundAlexander Healy, Tali Kaufman, Guy N. Rothblum: A (de)constructive approach to program checking. STOC 2008: 143-152

Tali Kaufman, Madhu Sudan: Algebraic property testing: the role of invariance. STOC 2008: 403-412

Noga Alon, Tali Kaufman, Michael KrivelevichDana Ron: Testing Triangle-Freeness in General Graphs. SIAM J. Discrete Math. 22(2): 786-819 (2008)

Tali Kaufman, Madhu Sudan: Sparse Random Linear Codes are Locally Decodable and Testable. FOCS 2007: 590-600

Shafi GoldwasserDan GutfreundAlexander Healy, Tali Kaufman, Guy N. Rothblum: Verifying and decoding in constant depth. STOC 2007: 440-449

Noga AlonAlexandr Andoni, Tali Kaufman, Kevin MatulefRonitt RubinfeldNing Xie: Testing k-wise and almost k-wise independence. STOC 2007: 496-505

Noga AlonVenkatesan Guruswami, Tali Kaufman, Madhu Sudan: Guessing secrets efficiently via list decoding. ACM Transactions on Algorithms 3(4): (2007)

Research

Sub-linear Algorithms and Property Testing, Coding Theory, Graph Theory, Randomness in Computation, Approximation Algorithms, Combinatorics and Additive Combinatorics, Complexity Theory.