Xin Li

Yan Zhong

Electron. Colloquium Comput. Complex., 2023

Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Streaming and Query Once Space Complexity of Longest Increasing Subsequence.

[BibT_eX]

[DOI]

Yu Zheng

CoRR, 2023

Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Random Shortening of Linear Codes and Applications.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 29th International Conference, 2023

On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors.

[BibT_eX]

[DOI]

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Sunflowers and Robust Sunflowers from Randomness Extractors.

[BibT_eX]

[DOI]

Shachar Lovett

Jiapeng Zhang

Theory Comput., 2022

Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors.

[BibT_eX]

[DOI]

J. ACM, 2022

Low-Degree Polynomials Extract from Local Sources.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

2021

Efficient Document Exchange and Error Correcting Codes with Asymmetric Information.

[BibT_eX]

[DOI]

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

Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence.

[BibT_eX]

[DOI]

Alireza Farhadi

MohammadTaghi Hajiaghayi

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

Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence.

[BibT_eX]

[DOI]

Yu Zheng

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Nonmalleable Extractors and Codes, with Their Many Tampered Extensions.

[BibT_eX]

[DOI]

Vipul Goyal

SIAM J. Comput., 2020

Locally Decodable Codes with Randomized Encoding.

[BibT_eX]

[DOI]

Yu Zheng

IACR Cryptol. ePrint Arch., 2020

Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Space Efficient Deterministic Approximation of String Measures.

[BibT_eX]

[DOI]

CoRR, 2020

Non-malleable Codes, Extractors and Secret Sharing for Interleaved Tampering and Composition of Tampering.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 18th International Conference, 2020

Extractors and Secret Sharing Against Bounded Collusion Protocols.

[BibT_eX]

[DOI]

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

2019

Extractors for Adversarial Sources via Extremal Hypergraphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets.

[BibT_eX]

[DOI]

Bernhard Haeupler

Amirbehshad Shahrasbi

Ke Wu

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2018

Non-Malleable Extractors and Codes for Composition of Tampering, Interleaved Tampering and More.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2018

Sunflowers and Quasi-sunflowers from Randomness Extractors.

[BibT_eX]

[DOI]

Shachar Lovett

Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2018

Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Edit Errors with Block Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes.

[BibT_eX]

[DOI]

CoRR, 2018

Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets.

[BibT_eX]

[DOI]

Bernhard Haeupler

Amirbehshad Shahrasbi

Ke Wu

CoRR, 2018

A New Approach for Constructing Low-Error, Two-Source Extractors.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

Randomness Extraction in AC0 and with Small Locality.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

Near-Optimal Secret Sharing and Error Correcting Codes in AC0.

[BibT_eX]

[DOI]

Yuval Ishai

IACR Cryptol. ePrint Arch., 2017

A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets.

[BibT_eX]

[DOI]

Ke Wu

CoRR, 2017

Near-Optimal Secret Sharing and Error Correcting Codes in \mathsf AC^0 AC 0.

[BibT_eX]

[DOI]

Yuval Ishai

Proceedings of the Theory of Cryptography - 15th International Conference, 2017

2016

Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Randomness Extraction in AC<sup>0</sup> and with Small Locality.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Computing Approximate PSD Factorizations.

[BibT_eX]

[DOI]

Amitabh Basu

Michael Dinitz

Proceedings of the Approximation, 2016

2015

Improved Constructions of Two-Source Extractors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Extractors for Affine Sources with Polylogarithmic Entropy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Three-Source Extractors for Polylogarithmic Min-Entropy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Extractors for Sumset Sources.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Non-Malleable Extractors and Codes, with their Many Tampered Extensions.

[BibT_eX]

[DOI]

Vipul Goyal

Electron. Colloquium Comput. Complex., 2015

Non-malleable Condensers for Arbitrary Min-entropy, and Almost Optimal Protocols for Privacy Amplification.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 12th Theory of Cryptography Conference, 2015

2014

Privacy Amplification and Nonmalleable Extractors Via Character Sums.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications.

[BibT_eX]

[DOI]

Kai-Min Chung

Xiaodi Wu

Electron. Colloquium Comput. Complex., 2014

2013

Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Robust Pseudorandom Generators.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2012

New Independent Source Extractors with Exponential Improvement.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

2011

Non-Malleable Extractors for Entropy Rate <1/2.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Design Extractors, Non-Malleable Condensers and Privacy Amplification.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Privacy Amplification and Non-malleable Extractors via Character Sums.

[BibT_eX]

[DOI]

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

2010

Improved Constructions of Three Source Extractors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

A New Approach to Affine Extractors and Dispersers.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

On the Problem of Local Randomness in Privacy Amplification with an Active Adversary

[BibT_eX]

[DOI]

CoRR, 2010

2009

2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness.

[BibT_eX]

[DOI]

Yael Tauman Kalai