Frederic Green

Publications

• S. Fenner, F. Green, and S. Homer, "Fixed-Parameter Extrapolation and Aperiodic Order: Open Problems," in SIGACT News 49(3), pp. 35-47 (2018). PDF.

• Arkadev Chattopadhyay, F. Green, and H. Straubing, Circuit Complexity of Powering in Fields of Odd Characteristic, in Chicago Journal of Theoretical Computer Science 2016 (10), pp. 1-16 (August 3, 2016).

• S. Fenner, F. Green, and S. Homer, "Fixed-Parameter Extrapolation and Aperiodic Order," in arXiv:1212.2889 (Most recent new and improved version (6) submitted 8/29/2020; version 1 submitted 12/12/12, 12:12:12 EST).

• F. Green, D. Kreymer, and E. Viola, "Block-Symmetric Polynomials Correlate with Parity Better Than Symmetric," in Electronic Colloquium on Computational Complexity, report 160 (2012); PDF available here. Appeared in Computational Complexity (2017) doi:10.1007/s00037-017-0153-3. Published full text available here.

• F. Green, D. Kreymer, and E. Viola, "In Brute-Force Search of Correlation Bounds for Polynomials," in Electronic Colloquium on Computational Complexity, report 39 (2011); PDF available here.

• D. Bera, S. Fenner, F. Green and S. Homer, Universal Quantum Circuits, in arXiv:0804.2429 (2008). Appeared under the title "Efficient Universal Quantum Circuits", in COCOON 2009, pp. 418-428, LNCS 5609 (Springer-Verlag), and in Quantum Information and Computation 10 (2010) 16-27.

• F. Green and A. Roy, Uniqueness of optimal mod 3 circuits for parity, in Dagstuhl Seminar Proceedings 07411 "Algebraic Methods in Computational Complexity" (2008). Also available: powerpoint and keynote slides. Updated & corrected version appeared under the title Uniqueness of optimal mod 3 polynomials for parity in Journal of Number Theory 130 (2010), pp. 961 - 975, full text available on-line here. (Okay, you read the paper, you glanced at the slides. Now you can see the movie!)
• F. Green, Mathematics of Physics and Engineering by E. K. Blum and S. V. Lototsky (book review), SIGACT News 38, pp. 25 - 30 (2007). PDF.

• D. Bera, F. Green and S. Homer, Small-depth quantum circuits (survey article), SIGACT News 35, pp. 35 - 50 (2007). PDF.

• M. Fang, S. Fenner, F. Green, S. Homer, and Y. Zhang, Quantum lower bounds for fanout, arXiv preprint quant-ph/0312208. In Quantum Information and Computation 6 (2006), pp. 46-57.

• F. Green, A. Roy, and H. Straubing, Bounds on an exponential sum arising in Boolean circuit complexity, in Comptes Rendus 341(5) (2005), pp. 279-282.

• S. Fenner, F. Green, S. Homer, and Y. Zhang, Bounds on the power of constant-depth quantum circuits, arXiv preprint quant-ph/0312209. Appeared in Proceedings of Fundamentals of Computation Theory: 15th International Symposium, Lecture Notes in Computer Science 3623 (2005), pp. 44-55.

• F. Green, The Correlation Between Parity and Quadratic Polynomials Mod 3, in 17th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press (2002), pp. 65 -72. Appeared in Journal of Computer and System Sciences 69 (2004) pp. 28 - 44. PDF.

• F. Green, S. Homer, and C. Pollett, On the complexity of quantum ACC, Boston University CS Dept. preprint BUCS-TR-2000-003, and in arXiv.org, report quant-ph/0002057. In 15th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, (2000), pp. 250 - 262. Combined/expanded version with authors F. Green, S. Homer, C. Moore, and C. Pollett, under the title "Counting, fanout and the complexity of quantum ACC," appeared in Quantum Information and Computation 2 (2002), pp. 35 - 65. See arXiv preprint quant-ph/0106017.

• F. Green and R. Puim, Relativized separation of EQP from P$^{\mbox{NP}}$, in Information Processing Letters, 80 (2001) pp. 257 - 260. Postscript, PDF.

• F. Green, Computational Complexity, survey article in The Encyclopedia of Microcomputers, Volume 24, Supplement 3, (1999), pp. 23 - 44, Marcel Dekker, New York.

• S. Fenner, F. Green, S. Homer, and R. Puim, Quantum NP is Hard for PH, in Sixth Italian Conference on Theoretical Computer Science, World-Scientific, Singapore (1998) pp. 241 - 252, Postscript, PDF (see arXiv quant-ph arhives or ECCC for more current version). Appeared under the title, "Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy," in Proceedings of the Royal Society A (1999) 455, pp 3953 - 3966.

• F. Green , Exponential sums and circuits with a single threshold gate and mod-gates, in Theory of Computing Systems, 32 (1999) pp. 453 - 466. Postscript, PDF, LaTeX.

• S. Fenner, F. Green, S. Homer, A. Selman, T. Thierauf, and H. Vollmer, Complements of multivalued functions, in 11th Annual Symposium on Computational Complexity, IEEE Computer Society Press (1996) 260-269. Postscript, PDF. Also in Chicago Journal of Theoretical Computer Science (1999).

• J.-Y. Cai, F. Green, and T. Thierauf, On the correlation of symmetric functions, in Mathematical Systems Theory 29 (1996) 245-258. Postscript, PDF, LaTeX.

• F. Green, A complex-number Fourier technique for lower bounds on the mod-m degree, in Computational Complexity 9 (2000) 16-38. (Revised and expanded version of Lower bounds for depth-three circuits with equals and mod-gates,'' in 12th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag (1995) 71-82). Postscript, PDF, LaTeX.

• F. Green, J. Köbler, K. W. Regan, T. Schwentick, and J. Torán, The power of the middle bit of a #P function, in Journal of Computer and System Sciences 50(3), (1995) 456-467. Postscript, PDF, LaTeX

• F. Green, A lower bound for monotone perceptrons, in Mathematical Systems Theory 28 (1995) 283-298. Postscript, PDF, LaTeX

• F. Green, On the power of deterministic reductions to C$_=$P, in Mathematical Systems Theory 26 (1993), 215-233. Postscript, PDF, LaTeX

• F. Green, An oracle separating $\oplus$P from PP$^{\mbox{PH}}$, in Information Processing Letters 37 (1991) 149-153.

• F. Green, More about NP-completeness in the frustration model of spin-glasses, OR Spektrum 9 (1987) 161-165.

• F. Green, NP-complete problems in cellular automata, Complex Systems 1 (1987), 453-474.

• W. Celmaster, F. Green, R. Gupta, and E. Kovacs, The SU(2) deconfinement temperature on a body-centered hypercubic lattice, Phys. Rev. D33 (1986) 3022.

• W. Celmaster, F. Green, R. Gupta, and E. Kovacs, A vectorized Monte Carlo algorithm for computing Wilson line observables in SU(2) gauge theory on a BCH lattice, Comp. Phys. Comm. 36 (1985) 409.

• F. Green and F. Karsch, Monte Carlo simulation of SU(4) lattice gauge theory at finite temperature, Phys. Rev. D29 (1984) 2986.

• F. Green and F. Karsch, Mean field analysis of SU(N) deconfining transitions in the presence of dynamical quarks, Nucl. Phys. B238 (1984) 297.

• F. Green, The chiral phase transition at strong coupling, Phys. Lett. 133B (1983) 99.

• W. Celmaster and F. Green, Manifestly broken local symmetries at large N, Phys. Rev. Lett. 59 (1983) 1556.

• F. Green, Schwinger-Dyson equations in reduced, quenched, chiral models, Phys. Lett. 124B (1983) 501.

• F. Green, There is no roughening singularity at finite temperature, Nucl. Phys. B215[FS7] (1983) 349.

• F. Green, Strong coupling expansions for the string tension at finite temperature, Nucl. Phys. B215[FS7] (1983) 83.

• F. Green and S. Samuel, Calculating the large-N phase transition in gauge and matrix models, Nucl.Phys. B194 (1982) 107.

• F. Green and S. Samuel, The large-N phase transition in the U(N) chiral models, Phys. Lett. 103B (1981) 110.

• F. Green and S. Samuel, The large-N phase transition in the U(N) lattice gauge theory, Phys. Lett. 103B (1981) 48.

• F. Green and S. Samuel, Chiral models: their implication for gauge theories and large N, Nucl. Phys. B190[FS3] (1981) 113.

• I. Bars and F. Green, Complete integration of U(N) lattice gauge theory in a large N limit, Phys. Rev. D20 (1979) 3311.

• I. Bars and F. Green, Gauge invariant quantum variables in QCD, Nucl. Phys. B148 (1979) 445. Amazingly enough, preprint is available in PDF.

• I. Bars and F. Green, QCD in the axial gauge: boundary terms and Poincaré invariance, Nucl. Phys. B142 (1978) 157.

  ...and from the depths of time, an artifact from a few days spent in my youth as a real experimentalist:

• P. Stoler, N. N. Kaushal, F. Green, E. Harms and L. Laroze, Total Neutron Cross Sections in Deuterium below 1000 keV, Phys. Rev. Lett. 29 (1972) 1745 - 1748.

Back to Fred Green's Main Page