On modp transversals

Combinatorica - Tập 11 - Trang 17-22 - 1991
Jeff Kahn1, Roy Meshulam2
1Center for Operations Research, Rutgers University, New Brunswick, USA
2Department of Mathematics and Center for Operations Research, Rutgers University, New Brunswick, USA

Tài liệu tham khảo

D. Barrington: Bounded-width polynomial-size branching programs recognize exactly those languages in NC,Proc. 18 th ACM STOC,1986. R. Boppana, andM. Sipser: The complexity of finite function, preprint. A. A. Razborov: Lower bounds on the size of bounded depth networks over a complete basis with logical addition,Matematischi Zametki 41:4, 598–607 (in Russian). English translation inMathematical Notes of the Academy of Sciences of the USSR 41:4, 333–338. K. T. Smith: The uncertainty principle on groups,IMA Preprint Series # 402, 1988. R. Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity,Proc. 19 th ACM STOC,1987.