Talks

Adversarial Poisoning Attacks on RL-driven energy pricing

Online Data Poisoning Attacks in Deep RL: Concerns for RL in Energy Demand Response

Two New PCPs and Their Applications

I will present two relatively new types of Probabilistically Checkable Proofs (PCPs) and their various applications. Smooth and Strong PCPs and their applications to hardness of approximation under (Bilu—Linial) stability guarantees. Rectangular PCPs and their applications to matrix rigidity. No prior knowledge of any of the above topics (especially PCPs) is expected. Based, in part, on a joint work with Amey Bhangale, Prahladh Harsha, and Avishay Tal.

Rigid Matrices From Rectangular PCPs

In this talk, I will focus on introducing and motivating rectangular PCPs, and their application to matrix rigidity. No prior knowledge in PCPs is assumed. Based on “Rigid Matrices From Rectangular PCPs”, Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal, 2020. https://eccc.weizmann.ac.il/report/2020/075/

Rigid Matrices From Rectangular PCPs

Based on “Rigid Matrices From Rectangular PCPs”, Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal, 2020. https://eccc.weizmann.ac.il/report/2020/075/

Smooth and Strong PCPs

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and any incorrect claim is rejected with high probability regardless of the given alleged proof. But what about incorrect proofs of correct claims? In a strong PCP, an alleged proof is rejected with probability proportional to its distance from a correct proof. For applications to hardness of approximation, it is useful to have strong PCPs in which each bit in the proof is equally likely to be queried.

Smooth and Strong PCPs

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and any incorrect claim is rejected with high probability regardless of the given alleged proof. But what about incorrect proofs of correct claims? In a strong PCP, an alleged proof is rejected with probability proportional to its distance from a correct proof. For applications to hardness of approximation, it is useful to have strong PCPs in which each bit in the proof is equally likely to be queried.

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

Based on Smooth and Strong PCPs.