6 citations · 9 across the 15 of their papers we have counts for
16 papers
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…
Split-State Non-Malleable Codes and Secret Sharing Schemes for Quantum Messages
Naresh Goud Boddu, Vipul Goyal, Rahul Jain +1
Non-malleable codes are fundamental objects at the intersection of cryptography and coding theory. These codes provide security guarantees even in settings where error correction a…
Computational Quantum Secret Sharing
Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang +1
Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties so that certain subsets can reconstruct the secret, while unauthorized subs…
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…
Low-Degree Polynomials Extract from Local Sources
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman +2
We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in…
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
Ryan Gabrys, Venkatesan Guruswami, João Ribeiro +1
We consider the problem of designing low-redundancy codes in settings where one must correct deletions in conjunction with substitutions or adjacent transpositions; a combination o…
Effects of Quantization on the Multiple-Round Secret-Key Capacity
Onur Günlü, Ueli Maurer, João Ribeiro
We consider the strong secret key (SK) agreement problem for the satellite communication setting, where a satellite chooses a common binary phase shift keying modulated input for t…
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…
AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing
Ryan Gabrys, Srilakshmi Pattabiraman, Vishal Rana +4
The first part of the paper presents a review of the gold-standard testing protocol for Covid-19, real-time, reverse transcriptase PCR, and its properties and associated measuremen…
Non-Asymptotic Capacity Upper Bounds for the Discrete-Time Poisson Channel with Positive Dark Current
Mahdi Cheraghchi, João Ribeiro
We derive improved and easily computable upper bounds on the capacity of the discrete-time Poisson channel under an average-power constraint and an arbitrary constant dark current…
Group Testing with Runlength Constraints for Topological Molecular Storage
Abhishek Agarwal, Olgica Milenkovic, Srilakshmi Pattabiraman +1
Motivated by applications in topological DNA-based data storage, we introduce and study a novel setting of Non-Adaptive Group Testing (NAGT) with runlength constraints on the colum…
An Overview of Capacity Results for Synchronization Channels
Mahdi Cheraghchi, João Ribeiro
Synchronization channels, such as the well-known deletion channel, are surprisingly harder to analyze than memoryless channels, and they are a source of many fundamental problems i…
Coded trace reconstruction
Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic +1
Motivated by average-case trace reconstruction and coding for portable DNA-based storage systems, we initiate the study of \emph{coded trace reconstruction}, the design and analysi…
Simple Codes and Sparse Recovery with Fast Decoding
Mahdi Cheraghchi, João Ribeiro
Construction of error-correcting codes achieving a designated minimum distance parameter is a central problem in coding theory. In this work, we study a very simple construction of…
Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels
Mahdi Cheraghchi, João Ribeiro
We study natural examples of binary channels with synchronization errors. These include the duplication channel, which independently outputs a given bit once or twice, and geometri…
Structural Results and Improved Upper Bounds on the Capacity of the Discrete-Time Poisson Channel
Mahdi Cheraghchi, João Ribeiro
New capacity upper bounds are presented for the discrete-time Poisson channel with no dark current and an average-power constraint. These bounds are a simple consequence of techniq…