Symmetric Functions Capture General Functions

1. Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. J. Assn. Comp. Mach. 45, 501–555 (1998)

   MathSciNet  MATH  Google Scholar 

2. Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. Assn. Comp. Mach. 45, 70–122 (1998)

   MathSciNet  MATH  Google Scholar 

3. Arora, S., Sudan, M.: Improved low-degree testing and its applications. Combinatorica 23(3), 365–426 (2003)

   Article  MathSciNet  MATH  Google Scholar 

4. Assumus Jr., E.F., Key, J.D.: Polynomial codes and Finite Geometries in Handbook of Coding Theory. In: Pless Jr., V.S., Huffman, W.C. (eds.), vol. II, ch.16. Elsevier, Amsterdam (1998)

   Google Scholar 

5. Baur, W., Strassen, V.: The complexity of partial derivatives. Theor. Comp. Sci. 22, 317–330 (1982)

   Article  MathSciNet  Google Scholar 

6. Beame, P., Brisson, E., Ladner, R.: The complexity of computing symmetric functions using threshold circuits. Theor. Comp. Sci. 100, 253–265 (1992)

   Article  MathSciNet  MATH  Google Scholar 

7. Beigel, R., Tarui, J.: On ACC. In: Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science, pp. 783–792 (1991)

   Google Scholar 

8. Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proc. 15th Annual ACM Symposium on the Theory of Computing, pp. 80–86 (1983)

   Google Scholar 

9. Dixon, J.D., Panario, D.: The degree of the splitting field of a random polynomial over a finite field. The Electronic Journal of Combinatorics 11(1) (2004), http://www.combinatorics.org/Volume_11/Abstracts/v11i1r70.html

10. Furst, M., Saxe, J., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Sys. Thy. 17, 13–27 (1984)

    Article  MathSciNet  MATH  Google Scholar 

11. Grigoriev, D., Karpinski, M.: An exponential lower bound for depth 3 arithmetic circuits. In: Proc. 30th Annual ACM Symposium on the Theory of Computing, pp. 577–582 (1998)

    Google Scholar 

12. Grigoriev, D., Razborov, A.: Exponential lower bounds for depth 3 algebraic circuits in algebras of functions over finite fields. Applicable Algebra in Engineering, Communication, and Computing 10, 465–487 (2000) (preliminary version FOCS 1998)

    Article  MathSciNet  MATH  Google Scholar 

13. Grolmusz, V.: Computing elementary symmetric polynomials with a sub-polynomial number of multiplications. SIAM Journal on Computing 32, 2002–02 (2002)

    MathSciNet  Google Scholar 

14. Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. Random Struct. Algorithms 35(2), 163–193 (2009)

    Article  MathSciNet  MATH  Google Scholar 

15. Kaufman, T., Ron, D.: Testing polynomials over general fields. SIAM Journal on Computing 36(3), 779–802 (2006)

    Article  MathSciNet  MATH  Google Scholar 

16. Klinger, A.: The Vandermonde matrix. The American Mathematical Monthly 74(5), 571–574 (1967)

    Article  MathSciNet  MATH  Google Scholar 

17. Lu, C.J.: An exact characterization of symmetric functions in qAC⁰[2]. In: Proc. 4th International Combinatorics and Computing Conference, pp. 167–173 (1998)

    Google Scholar 

18. Razborov, A.: Lower bounds for the size of circuits of bounded depth with basis { ∧ , ⊕ }. Mathematical Notes (formerly of the Academy of Natural Sciences of the USSR) 41, 333–338 (1987)

    Article  MathSciNet  MATH  Google Scholar 

19. Razborov, A.: On the method of approximations. In: Proc. 21st Annual ACM Symposium on the Theory of Computing, pp. 167–176 (1989)

    Google Scholar 

20. Shoup, V.: A computational introduction to number theory and algebra. Cambridge University Press, New York (2008)

    Google Scholar 

21. Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: Proc. 19th Annual ACM Symposium on the Theory of Computing, pp. 77–82 (1987)

    Google Scholar 

Download references