New lower bounds for probabilistic degree and AC0 with parity gates.
作者： Emanuele Viola
DOI:
关键词: Discrete mathematics 、 Parity (mathematics) 、 Probabilistic logic 、 Computer science
摘要:
weizmann.ac.il参考文章(15)
Eli Ben-Sasson, Emanuele Viola, Short PCPs with Projection Queries Automata, Languages, and Programming. pp. 163- 173 ,(2014) , 10.1007/978-3-662-43948-7_14
Ryan Williams, Josh Alman, Probabilistic Polynomials and Hamming Nearest Neighbors arXiv: Data Structures and Algorithms. ,(2015) , 10.1109/FOCS.2015.18
M. Ajtai, A non-linear time lower bound for Boolean branching programs foundations of computer science. pp. 60- 70 ,(1999) , 10.1109/SFFCS.1999.814578
Stephen A. Cook, A hierarchy for nondeterministic time complexity Journal of Computer and System Sciences. ,vol. 7, pp. 343- 353 ,(1973) , 10.1016/S0022-0000(73)80028-5
László Babai, Noam Nisant, Márió Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs Journal of Computer and System Sciences. ,vol. 45, pp. 204- 232 ,(1992) , 10.1016/0022-0000(92)90047-M
Ashok K. Chandra, Merrick L. Furst, Richard J. Lipton, Multi-party protocols symposium on the theory of computing. pp. 94- 99 ,(1983) , 10.1145/800061.808737
Daniel A. Spielman, Pseudorandom Bits for Polynomials foundations of computer science. pp. 41- 51 ,(2007) , 10.1109/FOCS.2007.56
Huacheng Yu, Ryan Williams, Amir Abboud, More applications of the polynomial method to algorithm design symposium on discrete algorithms. pp. 218- 230 ,(2015) , 10.5555/2722129.2722146
Josh Alman, Ryan Williams, Probabilistic rank and matrix rigidity symposium on the theory of computing. pp. 641- 652 ,(2017) , 10.1145/3055399.3055484
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Kaave Hosseini, Pseudorandom generators from polarizing random walks Proceedings of the 33rd Computational Complexity Conference. ,vol. 102, pp. 21- ,(2018) , 10.5555/3235586.3235587