A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.

We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.
Specifically, such constructions are presented for $t$-CLIQUE and $t$-SUM.
In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC).
The proof systems presented by us are
significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016)

Various expositional changes (incl switching Sections 4 and 5).

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.

We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.
Specifically, such constructions are presented for $t$-CLIQUE and $t$-SUM.
In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC).
The proof systems presented by us are
significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016)

Correcting a typo that made a minor unfavorable comparison (against our own construction).

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.

We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.
Specifically, such constructions are presented for $t$-CLIQUE and $t$-SUM.
In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC).
The proof systems presented by us are
significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016)

Added a few references we were not aware of, and a comment asserting that the proof system underlying Thm 1 applies also to verifying the number of violated conditions.

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.

We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.
Specifically, such constructions are presented for $t$-CLIQUE and $t$-SUM.
In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC).
The proof systems presented by us are
significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016)