Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PETER MANOHAR:
All reports by Author Peter Manohar:

TR19-070 | 14th May 2019
Alessandro Chiesa, Peter Manohar, Igor Shinkar

On Local Testability in the Non-Signaling Setting

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.

We present general results about the local testability of linear codes in the non-signaling ... more >>>


TR18-123 | 3rd July 2018
Alessandro Chiesa, Peter Manohar, Igor Shinkar

Probabilistic Checking against Non-Signaling Strategies from Linearity Testing

Revisions: 1

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is ... more >>>


TR18-067 | 9th April 2018
Alessandro Chiesa, Peter Manohar, Igor Shinkar

Testing Linearity against Non-Signaling Strategies

Revisions: 1

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.

We ... more >>>


TR17-110 | 22nd June 2017
Alessandro Chiesa, Peter Manohar, Igor Shinkar

On Axis-Parallel Tests for Tensor Product Codes

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>>




ISSN 1433-8092 | Imprint