Mahdi Cheraghchi

According to our database, Mahdi Cheraghchi authored at least 61 papers between 2005 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

Simple Codes and Sparse Recovery with Fast Decoding.

Mahdi Cheraghchi, João Ribeiro

SIAM J. Discret. Math., June, 2023

Where Quantum Complexity Helps Classical Complexity.

Arash Vaezi, Mahdi Cheraghchi, 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.

Anantham Nambiar, Chao Pan, Vishal Rana, Mahdi Cheraghchi, João Ribeiro, Sergei Maslov, Olgica Milenkovic

CoRR, 2023

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ<i>_p</i> Norms.

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro

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

2022

Mean-Based Trace Reconstruction Over Oblivious Synchronization Channels.

Mahdi Cheraghchi, Joseph Downs, João Ribeiro, Alexandra Veliche

IEEE Trans. Inf. Theory, 2022

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

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro

Electron. Colloquium Comput. Complex., 2022

2021

An Overview of Capacity Results for Synchronization Channels.

Mahdi Cheraghchi, João Ribeiro

IEEE Trans. Inf. Theory, 2021

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

Thach V. Bui, Mahdi Cheraghchi, Isao Echizen

IEEE Trans. Inf. Theory, 2021

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

Mahdi Cheraghchi, João Ribeiro

IEEE Commun. Lett., 2021

One-way Functions and Partial MCSP.

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2021

Semiquantitative Group Testing in at Most Two Rounds.

Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic

Proceedings of the IEEE International Symposium on Information Theory, 2021

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

Mahdi Cheraghchi, Joseph Downs, João Ribeiro, Alexandra Veliche

Proceedings of the IEEE International Symposium on Information Theory, 2021

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

Thach V. Bui, Mahdi Cheraghchi, Thuc Dinh Nguyen

Proceedings of the IEEE International Symposium on Information Theory, 2021

One-Way Functions and a Conditional Variant of MKTP.

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

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

List Learning with Attribute Noise.

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

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

2020

Coded Trace Reconstruction.

Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, João Ribeiro

IEEE Trans. Inf. Theory, 2020

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

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

Electron. Colloquium Comput. Complex., 2020

Leakage-Resilient Secret Sharing in Non-Compartmentalized Models.

Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang

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

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

Mahdi Cheraghchi, 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.

Mahdi Cheraghchi, João Ribeiro

IEEE Trans. Inf. Theory, 2019

Expressions for the Entropy of Basic Discrete Distributions.

Mahdi Cheraghchi

IEEE Trans. Inf. Theory, 2019

Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels.

Mahdi Cheraghchi, João Ribeiro

IEEE Trans. Inf. Theory, 2019

Efficiently Decodable Non-Adaptive Threshold Group Testing.

Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen

IEEE Trans. Inf. Theory, 2019

Capacity Upper Bounds for Deletion-type Channels.

Mahdi Cheraghchi

J. ACM, 2019

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

Electron. Colloquium Comput. Complex., 2019

Nearly optimal robust secret sharing.

Mahdi Cheraghchi

Des. Codes Cryptogr., 2019

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

Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen

CoRR, 2019

Non-Malleable Secret Sharing against Affine Tampering.

Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang

CoRR, 2019

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

Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen

CoRR, 2019

Non-Malleable Codes against Active Physical Layer Adversary.

Fuchun Lin, Reihaneh Safavi-Naini, Mahdi Cheraghchi, Huaxiong Wang

Proceedings of the IEEE International Symposium on Information Theory, 2019

2018

Local Testing of Lattices.

Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu

SIAM J. Discret. Math., 2018

AC⁰∘MOD₂ lower bounds for the Boolean Inner Product.

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

J. Comput. Syst. Sci., 2018

Secret Sharing with Binary Shares.

Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang

IACR Cryptol. ePrint Arch., 2018

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

Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen

CoRR, 2018

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

Mahdi Cheraghchi, João Ribeiro

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

Expressions for the Entropy of Binomial-Type Distributions.

Mahdi Cheraghchi

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

2017

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.

Mahdi Cheraghchi, Piotr Indyk

ACM Trans. Algorithms, 2017

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

Mahdi Cheraghchi, Venkatesan Guruswami

J. Cryptol., 2017

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

Fuchun Lin, Reihaneh Safavi-Naini, Mahdi Cheraghchi, Huaxiong Wang

CoRR, 2017

2016

Local Testing for Membership in Lattices.

Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu

Electron. Colloquium Comput. Complex., 2016

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

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

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

2015

AC⁰ \circ MOD₂ lower bounds for the Boolean Inner Product.

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

Electron. Colloquium Comput. Complex., 2015

2013

Capacity of Non-Malleable Codes.

Mahdi Cheraghchi, Venkatesan Guruswami

Electron. Colloquium Comput. Complex., 2013

Noise-resilient group testing: Limitations and constructions.

Mahdi Cheraghchi

Discret. Appl. Math., 2013

Improved Constructions for Non-adaptive Threshold Group Testing.

Mahdi Cheraghchi

Algorithmica, 2013

2012

Graph-Constrained Group Testing.

Mahdi Cheraghchi, Amin Karbasi, Soheil Mohajer, Venkatesh Saligrama

IEEE Trans. Inf. Theory, 2012

Invertible Extractors and Wiretap Protocols.

Mahdi Cheraghchi, Frédéric Didier, Amin Shokrollahi

IEEE Trans. Inf. Theory, 2012

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

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker

Electron. Colloquium Comput. Complex., 2012

Correctness and Corruption of Locally Decodable Codes.

Mahdi Cheraghchi, Anna Gál, Andrew Mills

Electron. Colloquium Comput. Complex., 2012

2011

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

Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, Martin Vetterli

IEEE Trans. Inf. Theory, 2011

Submodular Functions Are Noise Stable.

Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee

Electron. Colloquium Comput. Complex., 2011

Applications of Derandomization Theory in Coding

Mahdi Cheraghchi

CoRR, 2011

Coding-theoretic methods for sparse recovery.

Mahdi Cheraghchi

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

2010

Applications of Derandomization Theory in Coding.

Mahdi Cheraghchi

PhD thesis, 2010

Approximating Linear Threshold Predicates.

Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson

Electron. Colloquium Comput. Complex., 2010

Derandomization and group testing.

Mahdi Cheraghchi

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

2009

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

Mahdi Cheraghchi, Amin Shokrollahi

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

Capacity achieving codes From randomness conductors.

Mahdi Cheraghchi

Proceedings of the IEEE International Symposium on Information Theory, 2009

Bit precision analysis for compressed sensing.

Ehsan Ardestanizadeh, Mahdi Cheraghchi, Amin Shokrollahi

Proceedings of the IEEE International Symposium on Information Theory, 2009

Compressed sensing with probabilistic measurements: A group testing solution.

Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, Martin Vetterli

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

2005

On Matrix Rigidity and the Complexity of Linear Forms

Mahdi Cheraghchi

Electron. Colloquium Comput. Complex., 2005