Frederic Green, Publications

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