Minimizing DNF Formulas and AC0 Circuits Given a Truth Table
作者： Michael E. Saks , Toniann Pitassi , Lisa Hellerstein , Eric Allender , Paul McCabe
DOI:
关键词:
摘要:
hpi-web.de参考文章(36)
Nader H. Bshouty, Lynn Burroughs, On the Proper Learning of Axis Parallel Concepts conference on learning theory. pp. 287- 302 ,(2002) , 10.1007/3-540-45435-7_20
Vitaly Feldman, Hardness of approximate two-level logic minimization and PAC learning with membership queries Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06. pp. 363- 372 ,(2006) , 10.1145/1132516.1132569
Valentine Kabanets, Jin-Yi Cai, Circuit minimization problem symposium on the theory of computing. pp. 73- 79 ,(2000) , 10.1145/335305.335314
Ran Raz, A Parallel Repetition Theorem SIAM Journal on Computing. ,vol. 27, pp. 763- 803 ,(1998) , 10.1137/S0097539795280895
Rong-chii Duh, Martin Fürer, Approximation of k-set cover by semi-local optimization symposium on the theory of computing. pp. 256- 264 ,(1997) , 10.1145/258533.258599
Lisa Hellerstein, Vijay Raghavan, Exact learning of DNF formulas using DNF hypotheses symposium on the theory of computing. pp. 465- 473 ,(2002) , 10.1145/509907.509976
Luca Trevisan, Non-approximability results for optimization problems on bounded degree instances Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01. pp. 453- 461 ,(2001) , 10.1145/380752.380839
Nader H. Bshouty, Simple learning algorithms using divide and conquer Computational Complexity. ,vol. 6, pp. 174- 194 ,(1996) , 10.1007/BF01262930
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Ashok K. Chandra, George Markowsky, On the number of prime implicants Discrete Mathematics. ,vol. 24, pp. 7- 11 ,(1978) , 10.1016/0012-365X(78)90168-1