2024
Improved Explicit Near-Optimal Codes in the High-Noise Regimes.
Electron. Colloquium Comput. Complex., 2024
On $k$-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction.
Proceedings of the IEEE International Symposium on Information Theory, 2024
Two-Source and Affine Non-Malleable Extractors for Small Entropy.
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024
Improved Condensers for Chor-Goldreich Sources.
Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs.
Proceedings of the 39th Computational Complexity Conference, 2024
2023
Random Shortening of Linear Codes and Application.
Electron. Colloquium Comput. Complex., 2023
Streaming and Query Once Space Complexity of Longest Increasing Subsequence.
CoRR, 2023
Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023
Random Shortening of Linear Codes and Applications.
Proceedings of the Computing and Combinatorics - 29th International Conference, 2023
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors.
Proceedings of the 38th Computational Complexity Conference, 2023
2022
Sunflowers and Robust Sunflowers from Randomness Extractors.
Theory Comput., 2022
Improved Decoding of Expander Codes.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022
Low-Degree Polynomials Extract From Local Sources.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022
2021
Efficient Document Exchange and Error Correcting Codes with Asymmetric Information.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
Efficient Linear and Affine Codes for Correcting Insertions/Deletions.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence.
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.
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.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021
2020
Nonmalleable Extractors and Codes, with Their Many Tampered Extensions.
SIAM J. Comput., 2020
Locally Decodable Codes with Randomized Encoding.
IACR Cryptol. ePrint Arch., 2020
Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols.
Electron. Colloquium Comput. Complex., 2020
Space Efficient Deterministic Approximation of String Measures.
CoRR, 2020
Non-malleable Codes, Extractors and Secret Sharing for Interleaved Tampering and Composition of Tampering.
Proceedings of the Theory of Cryptography - 18th International Conference, 2020
Extractors for adversarial sources via extremal hypergraphs.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020
Extractors and Secret Sharing Against Bounded Collusion Protocols.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
2019
Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets.
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.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019
Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions.
Proceedings of the 34th Computational Complexity Conference, 2019
2018
Non-Malleable Extractors and Codes for Composition of Tampering, Interleaved Tampering and More.
IACR Cryptol. ePrint Arch., 2018
Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More.
Electron. Colloquium Comput. Complex., 2018
Edit Errors with Block Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes.
CoRR, 2018
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets.
CoRR, 2018
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
A New Approach for Constructing Low-Error, Two-Source Extractors.
Proceedings of the 33rd Computational Complexity Conference, 2018
Sunflowers and Quasi-Sunflowers from Randomness Extractors.
Proceedings of the Approximation, 2018
Randomness Extraction in AC0 and with Small Locality.
Proceedings of the Approximation, 2018
2017
Near-Optimal Secret Sharing and Error Correcting Codes in AC0.
IACR Cryptol. ePrint Arch., 2017
A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate.
Electron. Colloquium Comput. Complex., 2017
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets.
CoRR, 2017
Near-Optimal Secret Sharing and Error Correcting Codes in \mathsf AC^0 AC 0.
Proceedings of the Theory of Cryptography - 15th International Conference, 2017
Improved non-malleable extractors, non-malleable codes and independent source extractors.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
Non-malleable codes and extractors for small-depth circuits, and affine functions.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
2016
Randomness Extraction in AC<sup>0</sup> and with Small Locality.
Electron. Colloquium Comput. Complex., 2016
Extractors for sumset sources.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Non-malleable extractors and codes, with their many tampered extensions.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
Computing Approximate PSD Factorizations.
Proceedings of the Approximation, 2016
2015
Improved Constructions of Two-Source Extractors.
Electron. Colloquium Comput. Complex., 2015
Extractors for Affine Sources with Polylogarithmic Entropy.
Electron. Colloquium Comput. Complex., 2015
Non-malleable Condensers for Arbitrary Min-entropy, and Almost Optimal Protocols for Privacy Amplification.
Proceedings of the Theory of Cryptography - 12th Theory of Cryptography Conference, 2015
Three-Source Extractors for Polylogarithmic Min-Entropy.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015
2014
Privacy Amplification and Nonmalleable Extractors Via Character Sums.
SIAM J. Comput., 2014
Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications.
Electron. Colloquium Comput. Complex., 2014
2013
New independent source extractors with exponential improvement.
Proceedings of the Symposium on Theory of Computing Conference, 2013
Robust Pseudorandom Generators.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013
Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013
2012
Design extractors, non-malleable condensers and privacy amplification.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
Non-malleable Extractors, Two-Source Extractors and Privacy Amplification.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
2011
Non-Malleable Extractors for Entropy Rate <1/2.
Electron. Colloquium Comput. Complex., 2011
Privacy Amplification and Non-malleable Extractors via Character Sums.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
A New Approach to Affine Extractors and Dispersers.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011
Improved Constructions of Three Source Extractors.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011
2010
On the Problem of Local Randomness in Privacy Amplification with an Active Adversary
CoRR, 2010
2009
2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
2008
Network Extractor Protocols.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
2004
A Speaker Tracking Algorithm Based on Audio and Visual Information Fusion Using Particle Filter.
Proceedings of the Image Analysis and Recognition: International Conference, 2004