logo
  • Articles
  • Editors
  • Submit
  • Search
  • Home
  • About
  • Articles
  • Special Issues
  • Graduate Surveys
  • Library
  • Editors
  • Submit
  • Issues
  • Contact Us
  • Search
Articles under category:
Complexity
Vol 16, Article 13 (pp 1-30)
Monotone Circuit Lower Bounds from Resolution
by Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov
Vol 16, Article 7 (pp 1-50)
More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials
by Chin Ho Lee and Emanuele Viola
Vol 15, Article 17 (pp 1-20)
Separation of AC$^0[\oplus]$ Formulas and Circuits
by Ben Rossman and Srikanth Srinivasan
Vol 14, Article 5 (pp 1-27)
Randomized Query Complexity of Sabotaged and Composed Functions
by Shalev Ben-David and Robin Kothari
Vol 13, Article 10 (pp 1-19)
On the Hardness of Approximating Balanced Homogenous 3-Lin
by Johan Håstad and Rajsekar Manokaran
Vol 12, Article 9 (pp 1-23) [APRX-RND14 Spec Issue]
Communication Complexity of Set-Disjointness for All Probabilities
by Mika Göös and Thomas Watson
Vol 11, Article 14 (pp 357-393)
Non-Commutative Arithmetic Circuits with Division
by Pavel Hrubeš and Avi Wigderson