All reports by Author Igor Shinkar:

__
TR18-123
| 3rd July 2018
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### Probabilistic Checking against Non-Signaling Strategies from Linearity Testing

Revisions: 1

__
TR18-067
| 9th April 2018
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### Testing Linearity against Non-Signaling Strategies

Revisions: 1

__
TR18-008
| 10th January 2018
__

Tom Gur, Igor Shinkar#### An Entropy Lower Bound for Non-Malleable Extractors

__
TR17-110
| 22nd June 2017
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### On Axis-Parallel Tests for Tensor Product Codes

Alessandro Chiesa, Peter Manohar, Igor Shinkar

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 >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

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 >>>

Tom Gur, Igor Shinkar

A (k,\eps)-non-malleable extractor is a function nmExt : {0,1}^n x {0,1}^d -> {0,1} that takes two inputs, a weak source X~{0,1}^n of min-entropy k and an independent uniform seed s in {0,1}^d, and outputs a bit nmExt(X, s) that is \eps-close to uniform, even given the seed s and the ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

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 >>>