[an error occurred while processing this directive]


<h2>CCC 2013 Accepted papers and abstracts</h2>
<h3>(In order of submission)</h3>


[Show <a href="accept_abstracts.html">with abstracts</a>]

<hr>
<ul>

<li><b>The Correct Exponent for the Gotsman-Linial Conjecture</b><br/>
 Daniel Kane (Stanford University)

</li><br/>



<li><b> On Rigid Matrices and U-Polynomials</b><br/>
 Noga Alon (Tel-Aviv University),
Gil Cohen (Weizmann Institute of Science)

</li><br/>



<li><b>Formulas are exponentially stronger than monotone circuits in non-commutative setting</b><br/>
 Pavel Hrubes (University of Washington,
Seattle), Amir Yehudayoff (Technion-IIT, Israel)

</li><br/>




<li><b>Just a Pebble Game</b><br/>
 Siu Man Chan (UC Berkeley)

</li><br/>




<li><b>Quantum XOR Games</b><br/>
 Oded Regev (Courant Institute, New York University),  Thomas Vidick
(Massachusetts Institute of Technology)

</li><br/>



<li><b>Strong LTCs with inverse polylogarithmic rate and soundness</b><br/>
 Michael Viderman (Technion)

</li><br/>




<li><b>Two-message quantum interactive proofs and the quantum separability problem</b><br/>
Patrick Hayden (School of Computer
Science, McGill University), Kevin Milner (School of Computer Science,
McGill University), Mark M. Wilde (School of Computer Science, McGill University)

</li><br/>




<li><b>How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?</b><br/>
 Andris Ambainis (University of Latvia,
Riga), Ronald de Wolf (CWI and University of Amsterdam)

</li><br/>




<li><b>Approaching the chasm at depth four</b><br/>
 Ankit Gupta (Microsoft Research, India), Pritish Kamath
(Microsoft Research, India), Neeraj Kayal (Microsoft Research, India),
Ramprasad Saptharishi (Chennai Mathematical Institute)

</li><br/>




<li><b>Shared Randomness and Quantum Communication in the Multi-Party
Model</b><br/>
 Dmitry Gavinsky (NEC Laboratories America), Tsuyoshi Ito (NEC
Laboratories America), Guoming Wang (NEC Laboratories America; Computer
Science Division, UC Berkeley)

</li><br/>




<li><b>On the Power of Non-Adaptive Learning Graphs</b><br/>
 Aleksandrs Belovs (University of Latvia), Ansis Rosmanis (David R. Cheriton School of Computer Science and Institute for Quantum
Computing, University of Waterloo.)

</li><br/>


<li><b>Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits</b><br/>
 Yasuhiro Takahashi (NTT Communication
  Science Laboratories), Seiichiro Tani (NTT Communication Science Laboratories)
</li><br/>



<li><b>A Derandomized Switching Lemma and an improved Derandomization of AC0</b><br/>
 Luca Trevisan (Stanford University),
  TongKe Xue (Stanford University)

</li><br/>


<li><b>Random Arithmetic Formulas can be Reconstructed Efficiently</b><br/>
Ankit Gupta (Microsoft Research India),
Neeraj Kayal (Microsoft Research India),
Youming Qiao (Centre for Quantum Technologies, National University of Singapore)
</li><br/>




<li><b>Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover</b><br/>
 Sushant Sachdeva (Princeton University),
Rishi Saket (IBM T. J. Watson Research Center)

</li><br/>



<li><b> Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole
Principle</b><br/>
 Albert Atserias (UPC, Barcelona), Moritz M&uuml;ller (Kurt G&ouml;del
Research Center, Vienna), Sergi Oliva (UPC, Barcelona)

</li><br/>



<li><b>Superlinear lower bounds for multipass graph processing </b><br/>
 Venkatesan Guruswami (CMU), Krzysztof Onak (IBM Research) 

</li><br/>



<li><b>On the Parameterized and Approximation Hardness of Metric Dimension</b><br/>
 Sepp Hartung (Institut f&uuml;r
Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin,
Germany), Andr&eacute; Nichterlein (Institut f&uuml;r Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany)

</li><br/>



<li><b>Covering CSPs</b><br/>
 Irit Dinur (Weizmann Institute), Gillat Kol (Weizmann Institute)

</li><br/>



<li><b>The distinguishability of product distributions by read-once branching programs</b><br/>
 John Steinberger (Tsinghua University IIIS)

</li><br/>



<li><b>
An $O({n^{{1\over 2}+\epsilon}})$ Space Algorithm for Directed Planar
Reachability with Polynomial Running Time</b><br/>
 
T. Imai (Tokyo Institute of Technology),
K. Nakagawa (Tokyo Institute of Technology),
A. Pavan (Iowa State University),
N. V. Vinodchandran (University of Nebraska-Lincoln),
O. Watanabe (Tokyo Institute of Technology)

</li><br/>



<li><b>Short lists with short programs in short time</b><br/>
 Bruno Bauwens (Universit&eacute; de Lorraine),
                  Anton Makhlin (Moscow State University),
                  Nikolay Vereshchagin (Moscow State University),
                  Marius Zimand (Towson University)

</li><br/>



<li><b>Constructing hard functions from learning algorithms</b><br/>
 Adam Klivans (University of Texas at Austin), Pravesh Kothari
(University of Texas at Austin), Igor C. Oliveira (Columbia
University)

</li><br/>



<li><b>Approximating Boolean functions with depth-2 circuits</b><br/>
 Eric Blais (MIT), Li-Yang Tan (Columbia University)

</li><br/>




<li><b>Towards a Reverse Newman.s Theorem in Interactive Information Complexity</b><br/>
 Joshua Brody (Aarhus University), Harry
Buhrman (CWI Amsterdam and University of Amsterdam), Michal Koucky
(Mathematical Institute of Czech Academy of Sciences, Prague), Bruno
Loff (CWI Amsterdam), Florian Speelman (CWI Amsterdam), Nikolay
Vereshchagin (Moscow State University)

</li><br/>



<li><b>LS+ Lower Bounds from Pairwise Independence</b><br/>
 Madhur Tulsiani (TTI Chicago), Pratik Worah (University of Chicago)

</li><br/>



<li><b>On Medium-Uniformity and Circuit Lower Bounds</b><br/>
 Rahul Santhanam (University of Edinburgh), Ryan Williams (Stanford University)

</li><br/>





<li><b>Composition limits and separating examples
for some Boolean function complexity measures</b><br/>
 Justin Gilmer (Department of
Mathematics, Rutgers University), Michael Saks (Department of
Mathematics, Rutgers University), Srikanth Srinivasan (Department of Mathematics, IIT Bombay) 

</li><br/>


<li><b>On the Lattice Smoothing Parameter Problem</b><br/>
Kai-Min Chung (Cornell University),
Daniel Dadush (New York University),
Feng-Hao Liu (Brown University),
Chris Peikert (Georgia  Institute of Technology)
  
</li><br/>



</ul> 




</div>

</div>
</div>