51 citations · 146 across the 39 of their papers we have counts for
41 papers
Reductions Between Code Equivalence Problems
Mahdi Cheraghchi, Nikhil Shagrithaya, Alexandra Veliche
In this paper we present two reductions between variants of the Code Equivalence problem. We give polynomial-time Karp reductions from Permutation Code Equivalence (PCE) to both Li…
Semi-Quantitative Group Testing for Efficient and Accurate qPCR Screening of Pathogens with a Wide Range of Loads
Ananthan Nambiar, Chao Pan, Vishal Rana +4
Pathogenic infections pose a significant threat to global health, affecting millions of people every year and presenting substantial challenges to healthcare systems worldwide. Eff…
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all Norms
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami +1
We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any co…
Semiquantitative Group Testing in at Most Two Rounds
Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic
Semiquantitative group testing (SQGT) is a pooling method in which the test outcomes represent bounded intervals for the number of defectives. Alternatively, it may be viewed as an…
Mean-Based Trace Reconstruction over Oblivious Synchronization Channels
Mahdi Cheraghchi, Joseph Downs, João Ribeiro +1
Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors. It is known that trace…
Improved algorithms for non-adaptive group testing with consecutive positives
Thach V. Bui, Mahdi Cheraghchi, An T. H. Nguyen +1
The goal of group testing is to efficiently identify a few specific items, called positives, in a large population of items via tests. A test is an action on a subset of items whic…