Articles under category:
Average Case
Average Case
|
Vol 16, Article 9 (pp 1-12)
On the Complexity of Computing a Random Boolean Function Over the Reals by Pavel Hrubeš |
|
Vol 14, Article 9 (pp 1-55)
[CCC16 Spec Issue]
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits by Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan |
|
Vol 9, Article 30 (pp 897-945)
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream by Kai-Min Chung, Michael Mitzenmacher, and Salil Vadhan |
|
Vol 9, Article 19 (pp 617-651)
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems by Uriel Feige, Elchanan Mossel, and Dan Vilenchik |
|
Vol 3, Article 2 (pp 25-43)
Easily refutable subformulas of large random 3CNF formulas by Uriel Feige and Eran Ofek |
|
Vol 2, Article 8 (pp 147-172)
On Learning Random DNF Formulas Under the Uniform Distribution by Jeffrey C. Jackson and Rocco A. Servedio |