Mahdi Cheraghchi

132 papers A* 8A 6B 18Journal 91Unranked 8
YearRankTypeTitle / Venue / Authors
2025 J jnl
Optimal Erasure Codes and Codes on Graphs.
CoRR
Yeyuan Chen, Mahdi Cheraghchi, Nikhil Shagrithaya
2025 B conf
Reductions Between Code Equivalence Problems.
ISIT
Mahdi Cheraghchi, Nikhil Shagrithaya, Alexandra Veliche
2025 J jnl
Reductions Between Code Equivalence Problems.
CoRR
Mahdi Cheraghchi, Nikhil Shagrithaya, Alexandra Veliche
2025 J jnl
Reductions Between Code Equivalence Problems.
IACR Cryptol. ePrint Arch.
Mahdi Cheraghchi, Nikhil Shagrithaya, Alexandra Veliche
2024 J jnl
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP.
Theory Comput. Syst.
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida
2024 J jnl
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms.
SIAM J. Comput.
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro
2024 J jnl
Semi-quantitative group testing for efficient and accurate qPCR screening of pathogens with a wide range of loads.
BMC Bioinform.
Ananthan Nambiar, Chao Pan, Vishal Rana, Mahdi Cheraghchi, João Ribeiro, Sergei Maslov, Olgica Milenkovic
2023 A* conf
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ
STOC
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro
2023 J jnl
Semi-Quantitative Group Testing for Efficient and Accurate qPCR Screening of Pathogens with a Wide Range of Loads.
CoRR
Anantham Nambiar, Chao Pan, Vishal Rana, Mahdi Cheraghchi, João Ribeiro, Sergei Maslov, Olgica Milenkovic
2023 J jnl
Simple Codes and Sparse Recovery with Fast Decoding.
SIAM J. Discret. Math.
Mahdi Cheraghchi, João Ribeiro
2023 J jnl
Where Quantum Complexity Helps Classical Complexity.
CoRR
Arash Vaezi, Mahdi Cheraghchi, Seyed Mohammad Hussein Kazemi, Negin Bagheri Noghrehy, Seyed Mohsen Kazemi, Ali Movaghar, Mohammad Ghodsi
2022 J jnl
Mean-Based Trace Reconstruction Over Oblivious Synchronization Channels.
IEEE Trans. Inf. Theory
Mahdi Cheraghchi, Joseph Downs, João Ribeiro, Alexandra Veliche
2022 J jnl
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓ
Electron. Colloquium Comput. Complex.
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro
2022 J jnl
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all 𝓁
CoRR
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro
2021 J jnl
An Overview of Capacity Results for Synchronization Channels.
IEEE Trans. Inf. Theory
Mahdi Cheraghchi, João Ribeiro
2021 J jnl
Improved Non-Adaptive Algorithms for Threshold Group Testing With a Gap.
IEEE Trans. Inf. Theory
Thach V. Bui, Mahdi Cheraghchi, Isao Echizen
2021 B conf
Improved algorithms for non-adaptive group testing with consecutive positives.
ISIT
Thach V. Bui, Mahdi Cheraghchi, Thuc Dinh Nguyen
2021 J jnl
Improved algorithms for non-adaptive group testing with consecutive positives.
CoRR
Thach V. Bui, Mahdi Cheraghchi, Thuc Dinh Nguyen
2021 A conf
List Learning with Attribute Noise.
AISTATS
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
2021 B conf
Mean-Based Trace Reconstruction over Practically any Replication-Insertion Channel.
ISIT
Mahdi Cheraghchi, Joseph Downs, João Ribeiro, Alexandra Veliche
2021 J jnl
Mean-Based Trace Reconstruction over Practically any Replication-Insertion Channel.
CoRR
Mahdi Cheraghchi, Joseph Downs, João Ribeiro, Alexandra Veliche
2021 J jnl
Non-Asymptotic Capacity Upper Bounds for the Discrete-Time Poisson Channel With Positive Dark Current.
IEEE Commun. Lett.
Mahdi Cheraghchi, João Ribeiro
2021 A conf
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP.
STACS
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida
2021 — conf
One-Way Functions and a Conditional Variant of MKTP.
FSTTCS
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
2021 J jnl
One-way Functions and Partial MCSP.
Electron. Colloquium Comput. Complex.
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
2021 B conf
Semiquantitative Group Testing in at Most Two Rounds.
ISIT
Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic
2021 J jnl
Semiquantitative Group Testing in at Most Two Rounds.
CoRR
Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic
2020 J jnl
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.
ACM Trans. Comput. Theory
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
2020 J jnl
Coded Trace Reconstruction.
IEEE Trans. Inf. Theory
Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, João Ribeiro
2020 A* conf
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time.
FOCS
Mahdi Cheraghchi, Vasileios Nakos
2020 J jnl
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time.
CoRR
Mahdi Cheraghchi, Vasileios Nakos
2020 B conf
Improved non-adaptive algorithms for threshold group testing with a gap.
ISIT
Thach V. Bui, Mahdi Cheraghchi, Isao Echizen
2020 J jnl
Improved non-adaptive algorithms for threshold group testing with a gap.
CoRR
Thach V. Bui, Mahdi Cheraghchi, Isao Echizen
2020 A conf
Leakage-Resilient Secret Sharing in Non-Compartmentalized Models.
ITC
Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang
2020 J jnl
List Learning with Attribute Noise.
CoRR
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
2020 J jnl
Non-Asymptotic Capacity Upper Bounds for the Discrete-Time Poisson Channel with Positive Dark Current.
CoRR
Mahdi Cheraghchi, João Ribeiro
2020 J jnl
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida
2019 J jnl
An Overview of Capacity Results for Synchronization Channels.
CoRR
Mahdi Cheraghchi, João Ribeiro
2019 J jnl
Capacity Upper Bounds for Deletion-type Channels.
J. ACM
Mahdi Cheraghchi
2019 A* conf
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.
ICALP
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
2019 J jnl
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
2019 B conf
Coded Trace Reconstruction.
ITW
Mahdi Cheraghchi, João Ribeiro, Ryan Gabrys, Olgica Milenkovic
2019 J jnl
Coded trace reconstruction.
CoRR
Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, João Ribeiro
2019 J jnl
Efficient and error-tolerant schemes for non-adaptive complex group testing and its application in complex disease genetics.
CoRR
Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen
2019 J jnl
Efficiently Decodable Non-Adaptive Threshold Group Testing.
IEEE Trans. Inf. Theory
Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen
2019 J jnl
Expressions for the Entropy of Basic Discrete Distributions.
IEEE Trans. Inf. Theory
Mahdi Cheraghchi
2019 J jnl
Improved Upper Bounds and Structural Results on the Capacity of the Discrete-Time Poisson Channel.
IEEE Trans. Inf. Theory
Mahdi Cheraghchi, João Ribeiro
2019 J jnl
Improved encoding and decoding for non-adaptive threshold group testing.
CoRR
Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen
2019 J jnl
Nearly optimal robust secret sharing.
Des. Codes Cryptogr.
Mahdi Cheraghchi
2019 B conf
Non-Malleable Codes against Active Physical Layer Adversary.
ISIT
Fuchun Lin, Reihaneh Safavi-Naini, Mahdi Cheraghchi, Huaxiong Wang
2019 J jnl
Non-Malleable Secret Sharing against Affine Tampering.
CoRR
Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang
2019 A conf
Secret Sharing with Binary Shares.
ITCS
Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang
2019 J jnl
Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels.
IEEE Trans. Inf. Theory
Mahdi Cheraghchi, João Ribeiro
2019 B conf
Simple Codes and Sparse Recovery with Fast Decoding.
ISIT
Mahdi Cheraghchi, João Ribeiro
2019 J jnl
Simple Codes and Sparse Recovery with Fast Decoding.
CoRR
Mahdi Cheraghchi, João Ribeiro
2018 J jnl
A framework for generalized group testing with inhibitors and its potential application in neuroscience.
CoRR
Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen
2018 J jnl
AC
J. Comput. Syst. Sci.
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
2018 A* conf
Capacity upper bounds for deletion-type channels.
STOC
Mahdi Cheraghchi
2018 B conf
Efficiently Decodable Non-Adaptive Threshold Group Testing.
ISIT
Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen
2018 B conf
Expressions for the Entropy of Binomial-Type Distributions.
ISIT
Mahdi Cheraghchi
2018 B conf
Improved Capacity Upper Bounds for the Discrete-Time Poisson Channel.
ISIT
Mahdi Cheraghchi, João Ribeiro
2018 J jnl
Improved Capacity Upper Bounds for the Discrete-Time Poisson Channel.
CoRR
Mahdi Cheraghchi, João Ribeiro
2018 J jnl
Local Testing of Lattices.
SIAM J. Discret. Math.
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu
2018 J jnl
Secret Sharing with Binary Shares.
CoRR
Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang
2018 J jnl
Secret Sharing with Binary Shares.
IACR Cryptol. ePrint Arch.
Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang
2018 — conf
Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels.
Allerton
Mahdi Cheraghchi, João Ribeiro
2018 J jnl
Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels.
CoRR
Mahdi Cheraghchi, João Ribeiro
2017 J jnl
Capacity upper bounds for deletion-type channels.
CoRR
Mahdi Cheraghchi
2017 J jnl
Efficiently Decodable Non-Adaptive Threshold Group Testing.
CoRR
Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen
2017 J jnl
Expressions for the entropy of binomial-type distributions.
CoRR
Mahdi Cheraghchi
2017 J jnl
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.
ACM Trans. Algorithms
Mahdi Cheraghchi, Piotr Indyk
2017 J jnl
Non-Malleable Codes with Leakage and Applications to Secure Communication.
CoRR
Fuchun Lin, Reihaneh Safavi-Naini, Mahdi Cheraghchi, Huaxiong Wang
2017 J jnl
Non-malleable Coding Against Bit-Wise and Split-State Tampering.
J. Cryptol.
Mahdi Cheraghchi, Venkatesan Guruswami
2016 A* conf
AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product.
ICALP
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
2016 J jnl
Capacity of Non-Malleable Codes.
IEEE Trans. Inf. Theory
Mahdi Cheraghchi, Venkatesan Guruswami
2016 — conf
Local Testing for Membership in Lattices.
FSTTCS
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu
2016 J jnl
Local Testing for Membership in Lattices.
CoRR
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu
2016 J jnl
Local Testing for Membership in Lattices.
Electron. Colloquium Comput. Complex.
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu
2016 A* conf
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.
SODA
Mahdi Cheraghchi, Piotr Indyk
2016 B conf
Nearly optimal robust secret sharing.
ISIT
Mahdi Cheraghchi
2015 J jnl
AC
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
2015 J jnl
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.
CoRR
Mahdi Cheraghchi, Piotr Indyk
2015 J jnl
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Piotr Indyk
2015 J jnl
Nearly Optimal Robust Secret Sharing.
IACR Cryptol. ePrint Arch.
Mahdi Cheraghchi
2014 A conf
Capacity of non-malleable codes.
ITCS
Mahdi Cheraghchi, Venkatesan Guruswami
2014 B conf
Non-malleable Coding against Bit-Wise and Split-State Tampering.
TCC
Mahdi Cheraghchi, Venkatesan Guruswami
2013 J jnl
Capacity of Non-Malleable Codes.
CoRR
Mahdi Cheraghchi, Venkatesan Guruswami
2013 J jnl
Capacity of Non-Malleable Codes.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Venkatesan Guruswami
2013 J jnl
Capacity of Non-Malleable Codes.
IACR Cryptol. ePrint Arch.
Mahdi Cheraghchi, Venkatesan Guruswami
2013 J jnl
Improved Constructions for Non-adaptive Threshold Group Testing.
Algorithmica
Mahdi Cheraghchi
2013 J jnl
Noise-resilient group testing: Limitations and constructions.
Discret. Appl. Math.
Mahdi Cheraghchi
2013 J jnl
Non-Malleable Coding Against Bit-wise and Split-State Tampering.
CoRR
Mahdi Cheraghchi, Venkatesan Guruswami
2013 J jnl
Non-Malleable Coding Against Bit-wise and Split-State Tampering.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Venkatesan Guruswami
2013 J jnl
Non-Malleable Coding Against Bit-wise and Split-State Tampering.
IACR Cryptol. ePrint Arch.
Mahdi Cheraghchi, Venkatesan Guruswami
2013 A* conf
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.
SODA
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
2013 J jnl
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.
SIAM J. Comput.
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
2012 J jnl
Approximating Linear Threshold Predicates.
ACM Trans. Comput. Theory
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
2012 J jnl
Correctness and Corruption of Locally Decodable Codes.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Anna Gál, Andrew Mills
2012 J jnl
Graph-Constrained Group Testing.
IEEE Trans. Inf. Theory
Mahdi Cheraghchi, Amin Karbasi, Soheil Mohajer, Venkatesh Saligrama
2012 J jnl
Invertible Extractors and Wiretap Protocols.
IEEE Trans. Inf. Theory
Mahdi Cheraghchi, Frédéric Didier, Amin Shokrollahi
2012 J jnl
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
CoRR
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
2012 J jnl
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
2012 A* conf
Submodular functions are noise stable.
SODA
Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee
2011 J jnl
Applications of Derandomization Theory in Coding
CoRR
Mahdi Cheraghchi
2011 J jnl
Coding-Theoretic Methods for Sparse Recovery
CoRR
Mahdi Cheraghchi
2011 — conf
Coding-theoretic methods for sparse recovery.
Allerton
Mahdi Cheraghchi
2011 J jnl
Group Testing With Probabilistic Tests: Theory, Design and Application.
IEEE Trans. Inf. Theory
Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, Martin Vetterli
2011 J jnl
Submodular Functions Are Noise Stable
CoRR
Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee
2011 J jnl
Submodular Functions Are Noise Stable.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee
2010 — —
Applications of Derandomization Theory in Coding.
Mahdi Cheraghchi
2010 — conf
Approximating Linear Threshold Predicates.
APPROX-RANDOM
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
2010 J jnl
Approximating Linear Threshold Predicates.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
2010 J jnl
Derandomization and Group Testing
CoRR
Mahdi Cheraghchi
2010 — conf
Derandomization and group testing.
Allerton
Mahdi Cheraghchi
2010 J jnl
Graph-Constrained Group Testing
CoRR
Mahdi Cheraghchi, Amin Karbasi, Soheil Mohajer, Venkatesh Saligrama
2010 B conf
Graph-constrained group testing.
ISIT
Mahdi Cheraghchi, Amin Karbasi, Soheil Mohajer, Venkatesh Saligrama
2010 J jnl
Group Testing with Probabilistic Tests: Theory, Design and Application
CoRR
Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, Martin Vetterli
2010 J jnl
Improved Constructions for Non-adaptive Threshold Group Testing
CoRR
Mahdi Cheraghchi
2010 — conf
Improved Constructions for Non-adaptive Threshold Group Testing.
ICALP (1)
Mahdi Cheraghchi
2009 J jnl
Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties
CoRR
Mahdi Cheraghchi, Amin Shokrollahi
2009 A conf
Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties.
STACS
Mahdi Cheraghchi, Amin Shokrollahi
2009 J jnl
Bit Precision Analysis for Compressed Sensing
CoRR
Ehsan Ardestanizadeh, Mahdi Cheraghchi, Amin Shokrollahi
2009 B conf
Bit precision analysis for compressed sensing.
ISIT
Ehsan Ardestanizadeh, Mahdi Cheraghchi, Amin Shokrollahi
2009 J jnl
Capacity Achieving Codes From Randomness Conductors
CoRR
Mahdi Cheraghchi
2009 B conf
Capacity achieving codes From randomness conductors.
ISIT
Mahdi Cheraghchi
2009 J jnl
Compressed Sensing with Probabilistic Measurements: A Group Testing Solution
CoRR
Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, Martin Vetterli
2009 — conf
Compressed sensing with probabilistic measurements: A group testing solution.
Allerton
Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, Martin Vetterli
2009 J jnl
Invertible Extractors and Wiretap Protocols
CoRR
Mahdi Cheraghchi, Frédéric Didier, Amin Shokrollahi
2009 B conf
Invertible extractors and wiretap protocols.
ISIT
Mahdi Cheraghchi, Frédéric Didier, Amin Shokrollahi
2009 B conf
Noise-Resilient Group Testing: Limitations and Constructions.
FCT
Mahdi Cheraghchi
2008 J jnl
Noise-Resilient Group Testing: Limitations and Constructions
CoRR
Mahdi Cheraghchi
2005 J jnl
On Matrix Rigidity and the Complexity of Linear Forms
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi