Parity learning

<h2 id="noisy-version-learning-parity-with-noise"> Noisy version ("Learning Parity with Noise")</h2>
<p>In Learning Parity with Noise (LPN), the samples may contain some error. Instead of samples (<i>x</i>, <i>ƒ</i>(<i>x</i>)), the algorithm is provided with (<i>x</i>, <i>y</i>), where for random boolean 
  
    
      
        b
        ∈
        {
        0
        ,
        1
        }
      
    
    {\displaystyle b\in \{0,1\}}

</p><p>
  
    
      
        y
        =
        
          
            {
            
              
                
                  f
                  (
                  x
                  )
                  ,
                
                
                  
                    if 
                  
                  b
                
              
              
                
                  1
                  −
                  f
                  (
                  x
                  )
                  ,
                
                
                  
                    otherwise
                  
                
              
            
            
          
        
      
    
    {\displaystyle y={\begin{cases}f(x),&{\text{if }}b\\1-f(x),&{\text{otherwise}}\end{cases}}}

</p><p>The noisy version of the parity learning problem is conjectured to be hard<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> and is widely used in cryptography. <a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Learning_with_errors/rUoqf17k">Learning with errors</a></li></ul>

<ul><li>Avrim Blum, Adam Kalai, and Hal Wasserman, “Noise-tolerant learning, the parity problem, and the statistical query model,” J. ACM 50, no. 4 (2003): 506–519.</li>
<li>Adam Tauman Kalai, Yishay Mansour, and Elad Verbin, “On agnostic boosting and parity learning,” in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 629–638, <a href="http://portal.acm.org/citation.cfm?id=1374466">http://portal.acm.org/citation.cfm?id=1374466</a>.</li>
<li>Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84–93, <a href="http://portal.acm.org/citation.cfm?id=1060590.1060603">http://portal.acm.org/citation.cfm?id=1060590.1060603</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Wasserman, Hal; Kalai, Adam; Blum, Avrim (2000-10-15). "Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model". arXiv:cs/0010022. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Pietrzak, Krzysztof (2012). "Cryptography from Learning Parity with Noise" (PDF). SOFSEM 2012: Theory and Practice of Computer Science. Lecture Notes in Computer Science. Vol. 7147. pp. 99–114. doi:10.1007/978-3-642-27660-6_9. ISBN 978-3-642-27659-0. {{cite book}}: |journal= ignored (help) <a href="978-3-642-27659-0" target="_blank">978-3-642-27659-0</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Parity learning open-in-new

Parity learning