Short PCPs with projection queries
E Ben-Sasson, E Viola - … , ICALP 2014, Copenhagen, Denmark, July 8-11 …, 2014 - Springer
We construct a PCP for NTIME (2 n) with constant soundness, 2 n poly (n) proof length, and
poly (n) queries where the verifier's computation is simple: the queries are a projection of the …
poly (n) queries where the verifier's computation is simple: the queries are a projection of the …
Learning to learn: The co-evolution of an institution and its students
S Dziallas, S Fincher - 2014 IEEE Frontiers in Education …, 2014 - ieeexplore.ieee.org
In this study, we report on the student experience at Olin College, a small undergraduate
university in the United States with an explicit mission to transform engineering education …
university in the United States with an explicit mission to transform engineering education …
Turing and the development of computational complexity.
S Homer, AL Selman - 2014 - books.google.com
Turing's beautiful capture of the concept of computability by the “Turing machine” linked
computability to a device with explicit steps of operations and use of resources. This …
computability to a device with explicit steps of operations and use of resources. This …
Hierarchies against sublinear advice
L Fortnow, R Santhanam - Electronic Colloquium on …, 2014 - research.ed.ac.uk
We strengthen the non-deterministic time hierarchy theorem of [5, 15, 18] to show that the
lower bound holds against sublinear advice. More formally, we show that for any constants c …
lower bound holds against sublinear advice. More formally, we show that for any constants c …
[PDF][PDF] On verifying proofs in constant depth, and polynomial identity testing
K Sreenivasaiah - 2014 - hbni.ac.in
The thesis is divided into two main parts. The first part deals with proof systems computable
by Boolean circuit families that characterize the complexity class NC0 (bounded fanin …
by Boolean circuit families that characterize the complexity class NC0 (bounded fanin …