## 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