3 papers
cs.CC2025
Recovery Reductions, Conjectures, and Barriers
Tejas Nareddy, Abhishek Mishra
We introduce and initiate the study of a new model of reductions called the random noise model. In this model, the truth table of the function is corrupted on a randomly…
cs.CC2025
New Techniques for Constructing Rare-Case Hard Functions
Tejas Nareddy, Abhishek Mishra
We say that a function is rare-case hard against a given class of algorithms (the adversary) if all algorithms in the class can compute the function only on an -fraction of i…
cs.CC2024
Hardness Amplification via Group Theory
Tejas Nareddy, Abhishek Mishra
We employ techniques from group theory to show that, in many cases, counting problems on graphs are almost as hard to solve in a small number of instances as they are in all instan…