Irit Dinur<title> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> <meta name="keywords" content=""> <link href="/math/profile/design2.css" rel="stylesheet" type="text/css"> <script language="Javascript" src="/math/profile/footer.js" type="text/javascript"></script> <script language="Javascript" src="/math/profile/NavSet.js" type="text/javascript"></script> <script language="Javascript" src="/javascript/NavGen.js" type="text/javascript"></script> </head> <body> <div id="headleft"><img src="/math/profile/images/profile.gif"></div> <div id="headright"><img src="/math/profile/images/faculty.gif"></div> <div id="navigation"> <script language="JavaScript"> initHorNav(); horNav.displayNavHor("scientists"); </script> </div> <div id="content"> <body> <h2>Irit Dinur</h2> <p> </p> <p><img align=left border=1 src="pictures/irit.jpg" width="14%" "hspace=10" "vspace=10">  I am mainly interested in computational complexity, where we look at computational tasks and study their inherent difficulty level. This is measured either by comparison to other computational tasks, or by the amount of computational resources ( e.g. time, memory) required for completing the computation. <p> More specifically I am interested in Probabilistically Checkable Proofs (PCPs). A powerful characterization of the class NP asserts that NP proofs can be written in a special "PCP" format that enables ultra-efficient verification of these proofs. In other words, proofs can be written in a robust way that can tolerate a large amount of errors. <p> PCPs are also strongly connected with the complexity of approximation. When it is hard to solve a problem exactly, a natural approach is to seek an approximate solution. Using PCPs, one can prove that often finding an approximate solution is just as hard as solving the problem exactly. <p> On the technical side, my work on inapproximability has lead me to study analytic questions on Boolean functions and extremal combinatorics. Here I am mainly interested in "local to global" phenomena, where local conditions suffice for enforcing some global behavior. <p> </p> <p><strong>Recent Publications</strong></p> <ul> <li>[with Ehud Friedgut and Oded Regev] Independent Sets in Graph Powers are Almost Contained in Juntas. <em>GAFA (Geometric and Functional Analysis)</em> <b>18</b> (1) (2008) 77-97. <a href="http://www.cs.huji.ac.il/%7Edinuri/mypapers/DFR.pdf">(pdf)</a></li> <li>The PCP Theorem by gap amplification. <em>JACM</em> <b>54</b>, 3 (2007) Article No. 12. </li> <li>[with Madhu Sudan and Avi Wigderson] Robust local testability of tensor products of LDPC codes. <em>RANDOM 2006. </em> <a href="http://www.cs.huji.ac.il/%7Edinuri/mypapers/DSW06.pdf">(pdf)</a> <a href="http://www.cs.huji.ac.il/%7Edinuri/mypapers/DSW06.txt">(text)</a> </li> </ul> <p> </p> <p><a href="http://www.wisdom.weizmann.ac.il/~dinuri">Personal Web Page</a> </p> </div> <div id="footer"> <script language="javascript"> writeFooter(); </script></div> </body> </html> <script id="f5_cspm">(function(){var f5_cspm={f5_p:'HECFEMPLIODDFLMOGJKFDELGMPCNEAIDHEMJAAMLJJBJKGLOJEBPKKIGAEAJHFDNONABJEJGAAINJHJCMNOACOJJAAMNCGBLGJFGOONJBIILODADFNDPPJLLIKFPPJDH',setCharAt:function(str,index,chr){if(index>str.length-1)return str;return str.substr(0,index)+chr+str.substr(index+1);},get_byte:function(str,i){var s=(i/16)|0;i=(i&15);s=s*32;return((str.charCodeAt(i+16+s)-65)<<4)|(str.charCodeAt(i+s)-65);},set_byte:function(str,i,b){var s=(i/16)|0;i=(i&15);s=s*32;str=f5_cspm.setCharAt(str,(i+16+s),String.fromCharCode((b>>4)+65));str=f5_cspm.setCharAt(str,(i+s),String.fromCharCode((b&15)+65));return str;},set_latency:function(str,latency){latency=latency&0xffff;str=f5_cspm.set_byte(str,40,(latency>>8));str=f5_cspm.set_byte(str,41,(latency&0xff));str=f5_cspm.set_byte(str,35,2);return str;},wait_perf_data:function(){try{var wp=window.performance.timing;if(wp.loadEventEnd>0){var res=wp.loadEventEnd-wp.navigationStart;if(res<60001){var cookie_val=f5_cspm.set_latency(f5_cspm.f5_p,res);window.document.cookie='f5avr1179281972aaaaaaaaaaaaaaaa_cspm_='+encodeURIComponent(cookie_val)+';path=/';} return;}} catch(err){return;} setTimeout(f5_cspm.wait_perf_data,100);return;},go:function(){var chunk=window.document.cookie.split(/\s*;\s*/);for(var i=0;i<chunk.length;++i){var pair=chunk[i].split(/\s*=\s*/);if(pair[0]=='f5_cspm'&&pair[1]=='1234') {var d=new Date();d.setTime(d.getTime()-1000);window.document.cookie='f5_cspm=;expires='+d.toUTCString()+';path=/;';setTimeout(f5_cspm.wait_perf_data,100);}}}} f5