<p>Here are some recent papers on PCPs with small query complexity that I found interesting:</p>

<ul>
<li><a href="http://arxiv.org/pdf/1305.1979" rel="nofollow noreferrer">arxiv.org/pdf/1305.1979</a></li>
<li><a href="http://eccc.hpi-web.de/report/2013/179/download" rel="nofollow noreferrer">eccc.hpi-web.de/report/2013/179/download</a></li>
<li><a href="http://wisdom.weizmann.ac.il/~dinuri/mypapers/DH.pdf" rel="nofollow noreferrer">wisdom.weizmann.ac.il/~dinuri/mypapers/DH.pdf</a>   </li>
<li><a href="http://eccc.weizmann.ac.il/report/2015/085" rel="nofollow noreferrer">eccc.weizmann.ac.il/report/2015/085</a>   </li>
<li><a href="http://cs.utexas.edu/~danama/papers/par-rep/final3.pdf" rel="nofollow noreferrer">cs.utexas.edu/~danama/papers/par-rep/final3.pdf</a>   </li>
<li><a href="http://cs.utexas.edu/~danama/papers/par-rep-limit/paper.pdf" rel="nofollow noreferrer">cs.utexas.edu/~danama/papers/par-rep-limit/paper.pdf</a>   </li>
<li><a href="http://eccc.hpi-web.de/report/2016/160" rel="nofollow noreferrer">eccc.hpi-web.de/report/2016/160</a></li>
</ul>

<p>Also, <a href="https://www.math.ias.edu/csdm/files/08-09/rimpagliazzo_new_direct_product_testers_and_2_query.pdf" rel="nofollow noreferrer">this paper</a> is somewhat older, but it is interesting and can help understanding the context to some of the previous papers. In addition, if I may recommend a paper of my own, I think <a href="http://cs.haifa.ac.il/%7Eormeir/papers/derand_parallel_repetition_full.pdf" rel="nofollow noreferrer">this paper</a> contains open problems that might be useful.</p>

CC BY-SA 3.0
2017-03-05T23:31:52.057Z
2017-03-07T13:05:22.570Z
2017-03-07T13:05:22.570Z
Or Meir
<p>Hi I am taking an undergraduate taking a course in Probabilistic checkable Proofs. I will greatly appreciate if you can suggest some good research ideas and pertaining reading for someone who is just getting started. Thanks!</p>

CC BY-SA 3.0
2017-03-05T22:54:06.283Z
PCP is a very large area. Could you be more specific about which aspects of PCPs do you want to read about? Also, what did you already learn in your course?
Or Meir
CC BY-SA 3.0
2017-03-05T23:03:37.333Z
Topics covered include:

interactive proofs
IP=PSPACE
public to private coins
bounded communication/randomness
doubly-efficient interactive proofs (aka interactive proofs for muggles)
zero knowledge
basic probabilistic checking
exponential-size PCPs (Hadamard)
polynomial-size PCPs (Reed--Muller)
optimized probabilistic checking
redicing query complexity (proof composition, parallel repetition, 3-query PCPs, ...)
reducing proof length (routing, proximity testing to Reed--Solomon, ...) Reducing query complexity. I was thinking about reduction query complexity.
BrownGal
CC BY-SA 3.0
2017-03-07T17:30:22.487Z
@JoshuaGrochow Can you understand the down vote in this question? ... PS: I did not downvote it.
Tayfun Pay
CC BY-SA 3.0
2017-03-08T17:07:52.563Z
@JoshuaGrochow That was the second question that the user with user name Turbo asked where people got all touchy-feely about. Why aren't people getting touchy-feely about this question? What is wrong with this question that it got a down vote, but nobody wants to discuss why it got a down vote? Double standard as usual
Tayfun Pay
CC BY-SA 3.0
2017-03-09T04:42:49.727Z
I did not downvote, but "suggest some good research ideas and pertaining reading" for PCPs is in my opinion both subjective and too broad. But I personally don't feel too strongly about it
Sasho Nikolov
CC BY-SA 3.0
2017-03-11T18:02:18.043Z
[policy on project topic questions](http://meta.cstheory.stackexchange.com/q/802/)
Kaveh
<cc.complexity-theory><pcp><project-topic>
PCP research proposal
BrownGal
# PCP research proposal

(Asked by: username_0 on 2017-03-05)

Hi I am taking an undergraduate taking a course in Probabilistic checkable Proofs. I will greatly appreciate if you can suggest some good research ideas and pertaining reading for someone who is just getting started. Thanks!

**Tags:** cc.complexity-theory, pcp, project-topic

> **Comments:**
> **username_1**: PCP is a very large area. Could you be more specific about which aspects of PCPs do you want to read about? Also, what did you already learn in your course?  
> **username_0**: Topics covered include:  interactive proofs IP=PSPACE public to private coins bounded communication/randomness doubly-efficient interactive proofs (aka interactive proofs for muggles) zero knowledge basic probabilistic checking exponential-size PCPs (Hadamard) polynomial-size PCPs (Reed--Muller) optimized probabilistic checking redicing query complexity (proof composition, parallel repetition, 3-query PCPs, ...) reducing proof length (routing, proximity testing to Reed--Solomon, ...) Reducing query complexity. I was thinking about reduction query complexity.  
> **username_2**: @JoshuaGrochow Can you understand the down vote in this question? ... PS: I did not downvote it.  
> **username_2**: @JoshuaGrochow That was the second question that the user with user name Turbo asked where people got all touchy-feely about. Why aren't people getting touchy-feely about this question? What is wrong with this question that it got a down vote, but nobody wants to discuss why it got a down vote? Double standard as usual  
> **username_3**: I did not downvote, but "suggest some good research ideas and pertaining reading" for PCPs is in my opinion both subjective and too broad. But I personally don't feel too strongly about it  
> **username_4**: [policy on project topic questions](http://meta.cstheory.stackexchange.com/q/802/)  

---

## 1 answers

### Answer by username_1 on 2017-03-05. Score: 5

Here are some recent papers on PCPs with small query complexity that I found interesting:

* [arxiv.org/pdf/1305.1979](http://arxiv.org/pdf/1305.1979)
* [eccc.hpi-web.de/report/2013/179/download](http://eccc.hpi-web.de/report/2013/179/download)
* [wisdom.weizmann.ac.il/~dinuri/mypapers/DH.pdf](http://wisdom.weizmann.ac.il/~dinuri/mypapers/DH.pdf)
* [eccc.weizmann.ac.il/report/2015/085](http://eccc.weizmann.ac.il/report/2015/085)
* [cs.utexas.edu/~danama/papers/par-rep/final3.pdf](http://cs.utexas.edu/~danama/papers/par-rep/final3.pdf)
* [cs.utexas.edu/~danama/papers/par-rep-limit/paper.pdf](http://cs.utexas.edu/~danama/papers/par-rep-limit/paper.pdf)
* [eccc.hpi-web.de/report/2016/160](http://eccc.hpi-web.de/report/2016/160)

Also, [this paper](https://www.math.ias.edu/csdm/files/08-09/rimpagliazzo_new_direct_product_testers_and_2_query.pdf) is somewhat older, but it is interesting and can help understanding the context to some of the previous papers. In addition, if I may recommend a paper of my own, I think [this paper](http://cs.haifa.ac.il/%7Eormeir/papers/derand_parallel_repetition_full.pdf) contains open problems that might be useful.


---

