Avatar

Orr Paradise

PhD student

UC Berkeley

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 (to appear).

Preprint

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

More talks

About research other than my own

Slides and notes aren’t always identitcal to what was taught in class, and may be too elaborate/terse or contain my own original errors. If you encounter the latter, please let me know. Thank you!

The Margulis-Gabber-Galil Expanders [M73, GG81, T14]

Liquid Democracy [KMP18, GKMP18]

Pseudorandom Permutations of a Prescribed Type [NR02]

MAXCUT Is UGC-hard to Approximate [KKMO07]

Liquid Democracy [BBCV11, KMP18]

Teaching

Taught:

TA’ed:

Contact