Mahdi Cheraghchi

Nikhil Shagrithaya

CoRR, April, 2025

Reductions Between Code Equivalence Problems.

[BibT_eX]

[DOI]

Nikhil Shagrithaya

Alexandra Veliche

Proceedings of the IEEE International Symposium on Information Theory, 2025

2024

Semi-quantitative group testing for efficient and accurate qPCR screening of pathogens with a wide range of loads.

[BibT_eX]

[DOI]

BMC Bioinform., December, 2024

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms.

[BibT_eX]

[DOI]

SIAM J. Comput., 2024

2023

Where Quantum Complexity Helps Classical Complexity.

[BibT_eX]

[DOI]

Arash Vaezi

Seyed Mohammad Hussein Kazemi

Negin Bagheri Noghrehy

Seyed Mohsen Kazemi

Ali Movaghar

Mohammad Ghodsi

CoRR, 2023

Semi-Quantitative Group Testing for Efficient and Accurate qPCR Screening of Pathogens with a Wide Range of Loads.

[BibT_eX]

[DOI]

CoRR, 2023

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

Mean-Based Trace Reconstruction Over Oblivious Synchronization Channels.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2022

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓp Norms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

2021

An Overview of Capacity Results for Synchronization Channels.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

Non-Asymptotic Capacity Upper Bounds for the Discrete-Time Poisson Channel With Positive Dark Current.

[BibT_eX]

[DOI]

IEEE Commun. Lett., 2021

One-way Functions and Partial MCSP.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

One-Tape Turing Machine and Branching Program Lower Bounds for MCSP.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Semiquantitative Group Testing in at Most Two Rounds.

[BibT_eX]

[DOI]

Ryan Gabrys

Olgica Milenkovic

Proceedings of the IEEE International Symposium on Information Theory, 2021

Mean-Based Trace Reconstruction over Practically any Replication-Insertion Channel.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2021

Improved algorithms for non-adaptive group testing with consecutive positives.

[BibT_eX]

[DOI]

Thach V. Bui

Thuc Dinh Nguyen

Proceedings of the IEEE International Symposium on Information Theory, 2021

One-Way Functions and a Conditional Variant of MKTP.

[BibT_eX]

[DOI]

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

List Learning with Attribute Noise.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

Improved non-adaptive algorithms for threshold group testing with a gap.

[BibT_eX]

[DOI]

Thach V. Bui

Isao Echizen

Proceedings of the IEEE International Symposium on Information Theory, 2020

Leakage-Resilient Secret Sharing in Non-Compartmentalized Models.

[BibT_eX]

[DOI]

Proceedings of the 1st Conference on Information-Theoretic Cryptography, 2020

Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time.

[BibT_eX]

[DOI]

Vasileios Nakos

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

2019

Improved Upper Bounds and Structural Results on the Capacity of the Discrete-Time Poisson Channel.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2019

Expressions for the Entropy of Basic Discrete Distributions.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2019

Efficient and error-tolerant schemes for non-adaptive complex group testing and its application in complex disease genetics.

[BibT_eX]

[DOI]

CoRR, 2019

Non-Malleable Secret Sharing against Affine Tampering.

[BibT_eX]

[DOI]

CoRR, 2019

Improved encoding and decoding for non-adaptive threshold group testing.

[BibT_eX]

[DOI]

CoRR, 2019

Coded Trace Reconstruction.

[BibT_eX]

[DOI]

Proceedings of the 2019 IEEE Information Theory Workshop, 2019

Non-Malleable Codes against Active Physical Layer Adversary.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2019

Simple Codes and Sparse Recovery with Fast Decoding.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2019

Secret Sharing with Binary Shares.

[BibT_eX]

[DOI]

Karthekeyan Chandrasekaran

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.

[BibT_eX]

[DOI]

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

2018

Local Testing of Lattices.

[BibT_eX]

[DOI]

Venkata Gandikota

Elena Grigorescu

SIAM J. Discret. Math., 2018

AC0∘MOD2 lower bounds for the Boolean Inner Product.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2018

A framework for generalized group testing with inhibitors and its potential application in neuroscience.

[BibT_eX]

[DOI]

CoRR, 2018

Capacity upper bounds for deletion-type channels.

[BibT_eX]

[DOI]

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

Improved Capacity Upper Bounds for the Discrete-Time Poisson Channel.

[BibT_eX]

[DOI]

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

Expressions for the Entropy of Binomial-Type Distributions.

[BibT_eX]

[DOI]

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

Efficiently Decodable Non-Adaptive Threshold Group Testing.

[BibT_eX]

[DOI]

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual Allerton Conference on Communication, 2018

2017

Non-Malleable Codes with Leakage and Applications to Secure Communication.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.

[BibT_eX]

[DOI]

Piotr Indyk

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Nearly optimal robust secret sharing.

[BibT_eX]

[DOI]

Karthekeyan Chandrasekaran

Proceedings of the IEEE International Symposium on Information Theory, 2016

AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Local Testing for Membership in Lattices.

[BibT_eX]

[DOI]

Venkata Gandikota

Elena Grigorescu

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

2015

AC0 \circ MOD2 lower bounds for the Boolean Inner Product.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2014

Non-malleable Coding against Bit-Wise and Split-State Tampering.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 11th Theory of Cryptography Conference, 2014

Capacity of non-malleable codes.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.

[BibT_eX]

[DOI]

Ameya Velingker

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Correctness and Corruption of Locally Decodable Codes.

[BibT_eX]

[DOI]

Anna Gál

Andrew Mills

Electron. Colloquium Comput. Complex., 2012

Submodular functions are noise stable.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Group Testing With Probabilistic Tests: Theory, Design and Application.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2011

Applications of Derandomization Theory in Coding

[BibT_eX]

[DOI]

CoRR, 2011

Coding-theoretic methods for sparse recovery.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual Allerton Conference on Communication, 2011

2010

Applications of Derandomization Theory in Coding.

[BibT_eX]

[DOI]

PhD thesis, 2010

Graph-constrained group testing.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2010

Improved Constructions for Non-adaptive Threshold Group Testing.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Approximating Linear Threshold Predicates.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

Derandomization and group testing.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual Allerton Conference on Communication, 2010

2009

Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties.

[BibT_eX]

[DOI]

Amin Shokrollahi

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Invertible extractors and wiretap protocols.

[BibT_eX]

[DOI]

Frédéric Didier

Amin Shokrollahi

Proceedings of the IEEE International Symposium on Information Theory, 2009

Capacity achieving codes From randomness conductors.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2009

Bit precision analysis for compressed sensing.

[BibT_eX]

[DOI]

Ehsan Ardestanizadeh

Amin Shokrollahi

Proceedings of the IEEE International Symposium on Information Theory, 2009

Noise-Resilient Group Testing: Limitations and Constructions.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 17th International Symposium, 2009

Compressed sensing with probabilistic measurements: A group testing solution.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2005

On Matrix Rigidity and the Complexity of Linear Forms

[BibT_eX]

[DOI]