Avatar

Orr Paradise

PhD student

UC Berkeley

About

I am a first-year PhD student with the Theory of Computation group at UC Berkeley.

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.

Publications

(2019). Smooth and Strong PCPs. ITCS 2020.

Conference Preprint

Talks

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