Oded Goldreich, Muli Safra

The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1)))

is very complicated.

One source of difficulty is the technically involved

analysis of low-degree tests.

Here, we refer to the difficulty of obtaining strong results

regarding low-degree tests; namely, results of the type obtained and

used by ...
more >>>

Oded Goldreich

We survey known results regarding locally testable codes

and locally testable proofs (known as PCPs),

with emphasis on the length of these constructs.

Locally testability refers to approximately testing

large objects based on a very small number of probes,

each retrieving a single bit in the ...
more >>>

Mohammad Jahanara, Sajin Koroth, 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 >>>