Avatar

Orr Paradise

Hi,

I am a PhD student with the Theory of Computation group at UC Berkeley, where I am advised by Shafi Goldwasser and Avishay Tal. Before, I completed my MSc at the Weizmann Institute of Science, advised by Oded Goldreich.

I’m generally interested in theoretical computer science, and in particular computational complexity. I’ve been working on probabilistically checkable proofs and their connections with other areas of complexity theory. I’m also interested in societal aspects of theoretical computer science.

My pronouns are he/him.

Publications

Rigid Matrices From Rectangular PCPs


FOCS 2020.

Conference Preprint My talk Prahladh's talk

Smooth and Strong PCPs


computational complexity (2021); ITCS 2020.

Journal Conference Preprint Oded's choice

Talks

Rigid Matrices From Rectangular PCPs

Rigid Matrices From Rectangular PCPs

Smooth and Strong PCPs

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct …

Smooth and Strong PCPs

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct …

Incorrect (Probabilistic) Proofs for Correct Claims: Smooth and Strong PCPs

Teaching

Taught:

TA’ed:

Contact