COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

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

## A two prover one round game with strong soundnessAdd to your list(s) Download to your calendar using vCal - Khot, S (Courant Institute)
- Wednesday 30 March 2011, 15:30-16:30
- Seminar Room 1, Newton Institute.
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 q 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:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
Note that ex-directory lists are not shown. |
## Other listsCambridge University Student Pugwash Society Talks SCI Cambridge Science Talks CU Caving Club talks## Other talksBuilding World Class Life Science Businesses – The Good, The Bad and The Ugly THE MATHEMATICAL MAGIC OF MIXED REALITY Cambridge - Corporate Finance Theory Symposium September 2018 - Day 2 Intracellular Salmonella persisters The Revolution and Legacy of 1918 in Ukraine Delivering The Promise of the Internet of Things. How IoT systems can benefit transport, logistics and infrastructure |