University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > A two prover one round game with strong soundness

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

A two prover one round game with strong soundness

Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani .

Discrete Analysis

We show that for any large integer q, it is NP-hard to distinguish whether a two prover one round game with q6 answers has value close to 1 or at most O(1/q). The result is obtained by combining two new techniques: (i) An Inner PCP based on the “point versus subspace” test for linear functions. The test is analyzed Fourier analytically. (ii) The Outer/Inner PCP composition that relies on a certain “sub-code covering” property for Hadamard codes.

As an application, we show that unless NP has quasi-polynomial time deterministic algorithms, the Quadratic Programming Problem is inapproximable within factor (log n){1/6 – o(1)}.

The talk should be self-contained.

Joint work with Muli Safra

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Dept. of Engineering Trumpington Street, Baker Building - Sir Arthur Marshall Webinar & FW11, Computer Laboratory, William Gates Building. Justice and Communities Research Unit, Anglia Ruskin University

Other talks

Afternoon Break Title to be confirmed Disentangling preventative & ejective AGN feedback on a population basis with simulations, observations & machine learning Shape modes of CP^1 vortices Content, Caching and Kubernetes: Performance and User Experience in the Browser Tea and Coffee Break
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity