Mahdi Cheraghchi

SIAM J. Discret. Math., June, 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

Improved Non-Adaptive Algorithms for Threshold Group Testing With a Gap.

[BibT_eX]

[DOI]

Thach V. Bui

Isao Echizen

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

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

Coded Trace Reconstruction.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2020

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2019

Efficiently Decodable Non-Adaptive Threshold Group Testing.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2019

Capacity Upper Bounds for Deletion-type Channels.

[BibT_eX]

[DOI]

J. ACM, 2019

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Nearly optimal robust secret sharing.

[BibT_eX]

[DOI]

Des. Codes Cryptogr., 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

Non-Malleable Codes against Active Physical Layer Adversary.

[BibT_eX]

[DOI]

Karthekeyan Chandrasekaran

Proceedings of the IEEE International Symposium on Information Theory, 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

Secret Sharing with Binary Shares.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2018

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

[BibT_eX]

[DOI]

CoRR, 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

2017

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

[BibT_eX]

[DOI]

Karthekeyan Chandrasekaran

CoRR, 2017

2016

Local Testing for Membership in Lattices.

[BibT_eX]

[DOI]

Venkata Gandikota

Elena Grigorescu

Electron. Colloquium Comput. Complex., 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

2015

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.

[BibT_eX]

[DOI]

Piotr Indyk

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2013

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

[BibT_eX]

[DOI]

Ameya Velingker

SIAM J. Comput., 2013

Non-Malleable Coding Against Bit-wise and Split-State Tampering.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Capacity of Non-Malleable Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Noise-resilient group testing: Limitations and constructions.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2013

Improved Constructions for Non-adaptive Threshold Group Testing.

[BibT_eX]

[DOI]

Algorithmica, 2013

2012

Graph-Constrained Group Testing.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2012

Invertible Extractors and Wiretap Protocols.

[BibT_eX]

[DOI]

Frédéric Didier

Amin Shokrollahi

IEEE Trans. Inf. Theory, 2012

Correctness and Corruption of Locally Decodable Codes.

[BibT_eX]

[DOI]

Anna Gál

Andrew Mills

Electron. Colloquium Comput. Complex., 2012

2011

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

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2011

Submodular Functions Are Noise Stable.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Approximating Linear Threshold Predicates.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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

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]