Pseudorandom Generators in Propositional Proof Complexity
- 期刊名称SIAM Journal on Computing
- 作者Alekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi
- 卷第34卷
- 期第1期
- 印刷ISSN0097-5397
- 电子ISSN1095-7111
- 文件大小282.54KB
- 发表时间2004-01
- DOI10.1137/s0097539701389944
- 页码67-88
The Chow Parameters ProblemO'Donnell, Ryan; Servedio, Rocco A. · SIAM Journal on Computing · 2011
Testing HalfspacesMatulef, Kevin; O'Donnell, Ryan; Rubinfeld, Ronitt; Servedio, Rocco A. · SIAM Journal on Computing · 2010
Learning DNF from random walksNader H. Bshouty; Elchanan Mossel; Ryan O’Donnell; Rocco A. Servedio · 2005
Extremal properties of polynomial threshold functionsRyan O'Donnell; Rocco A. Servedio · 2008
Learning functions of k relevant variablesElchanan Mossel; Ryan O'Donnell; Rocco A. Servedio · 2004
Learning intersections and thresholds of halfspacesAdam R. Klivans; Ryan O'Donnell; Rocco A. Servedio · 2004
New degree bounds for polynomial threshold functionsRyan O’Donnell; Rocco A. Servedio · 2010
On Three-Dimensional PackingLi, Keqin; Cheng, Kam-Hoi · SIAM Journal on Computing · 1990
Priority Search TreesMcCreight, Edward M. · SIAM Journal on Computing · 1985
Scheduling Split IntervalsBar-Yehuda, R.; Halldórsson, M. M.; Naor, J. (S.); Shachnai, H.; Shapira, I. · SIAM Journal on Computing · 2006
Nondeterminism within $P^ * $Buss, Jonathan F.; Goldsmith, Judy · SIAM Journal on Computing · 1993
Optimization of Straight Line ProgramsAho, Alfred V.; Ullman, Jeffrey D. · SIAM Journal on Computing · 1972
Quantum Entanglement and Communication ComplexityBuhrman, Harry; Cleve, Richard; van Dam, Wim · SIAM Journal on Computing · 2001
On Classes of Program SchemataConstable, Robert L.; David, Gries · SIAM Journal on Computing · 1972
Bounded Concurrent Time-StampingDolev, Danny; Shavit, Nir · SIAM Journal on Computing · 1997