Next

__
TR24-141
| 12th September 2024
__

Tal Herman#### Public Coin Interactive Proofs for Label-Invariant Distribution Properties

__
TR24-140
| 11th September 2024
__

Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Rai, Jayalal Sarma#### Almost-catalytic Computation

__
TR24-139
| 11th September 2024
__

Jiatu Li, Edward Pyne, Roei Tell#### Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness

Next

Tal Herman

Assume we are given sample access to an unknown distribution $D$ over a large domain $[N]$. An emerging line of work has demonstrated that many basic quantities relating to the distribution, such as its distance from uniform and its Shannon entropy, despite being hard to approximate through the samples only, ... more >>>

Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Rai, Jayalal Sarma

Designing algorithms for space bounded models with restoration requirements on (most of) the space used by the algorithm is an important challenge posed about the catalytic computation model introduced by Buhrman et al (2014). Motivated by the scenarios where we do not need to restore unless $w$ is "useful", we ... more >>>

Jiatu Li, Edward Pyne, Roei Tell

This paper revisits the study of two classical technical tools in theoretical computer science: Yao's transformation of distinguishers to next-bit predictors (FOCS 1982), and the ``reconstruction paradigm'' in pseudorandomness (e.g., as in Nisan and Wigderson, JCSS 1994). Recent works of Pyne, Raz, and Zhan (FOCS 2023) and Doron, Pyne, and ... more >>>

Next