Frederic Green

According to our database, Frederic Green authored at least 52 papers between 1987 and 2022.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2022

Review of Feasible Computations and Provable Complexity Properties by Juris Hartmanis.

Frederic Green

SIGACT News, 2022

Review of "Mathematical Muffin Morsels - Nobody wants a small piece by William Gasarch, Erik Metz, Jacob Prinz, and Daniel Smolyak World Scientific, 2021 210 pages, Softcover, $59.99.".

Frederic Green

SIGACT News, 2022

Review of Complexity Dichotomies for Counting Problems Volume 1: Boolean Domain by Jin-Yi Cai and Xi Chen.

Frederic Green

SIGACT News, 2022

2021

Review of Three Lectures on Complexity and Black Holes by Leonard Susskind.

Frederic Green

SIGACT News, 2021

Review of Mathematics and Computation by Avi Wigderson.

Frederic Green

SIGACT News, 2021

The Book Review Column.

Frederic Green

SIGACT News, 2021

Review of A Short Course in Computational Geometry and Topology by Herbert Edelsbrunner.

Abdulai Gassama, Frederic Green

SIGACT News, 2021

2020

Review of Forbidden Configurations in Discrete Geometry by David Eppstein.

Frederic Green

SIGACT News, 2020

The Book Review Column1.

Frederic Green

SIGACT News, 2020

2019

Review of Handbook of Graph Theory, Combinatorial Optimization, and Algorithms.

Frederic Green

SIGACT News, 2019

Review of Modern Cryptography and Elliptic Curves, A Beginner's Guide by Thomas R. Shemanske.

Frederic Green

SIGACT News, 2019

Review of Number Theory: An Introduction via the Density of Primes, second edition.

Frederic Green

SIGACT News, 2019

2018

Joint Review of Quadratic Residues and Non-Residues by Steve Wright and The Quadratic Reciprocity Law by Oswald Baumgart Edited and translated by Franz Lemmermeyer.

Frederic Green

SIGACT News, 2018

Fixed-Parameter Extrapolation and Aperiodic Order: Open Problems.

Stephen A. Fenner, Frederic Green, Steven Homer

SIGACT News, 2018

2017

Review of Set Theory: A First Course by Daniel W. Cunningham.

Frederic Green

SIGACT News, 2017

Joint Review of The Magic of Math by Arthur Benjamin and How to Bake by Eugenia Cheng.

Frederic Green

SIGACT News, 2017

Review of Quantum Walks and Search Algorithms by Renato Portugal.

Frederic Green

SIGACT News, 2017

Review of Art in the Life of Mathematicians by Anna Kepes Szemerédi.

Frederic Green

SIGACT News, 2017

Block-symmetric polynomials correlate with parity better than symmetric.

Frederic Green, Daniel Kreymer, Emanuele Viola

Comput. Complex., 2017

2016

Review of: The Fascinating World of Graph Theory by Arthur Benjamin, Gary Chartrand and Ping Zhang.

Frederic Green

SIGACT News, 2016

Review of: Quantum Algorithms via Linear Algebra by Richard J. Lipton and Kenneth W. Regan.

Frederic Green

SIGACT News, 2016

Review of: Primality Testing for Beginners by Lasse Rempe-Gillen and Rebecca Waldecker.

Frederic Green

SIGACT News, 2016

Review of: The Nature of Computation by Cristopher Moore and Stephan Mertens.

Frederic Green

SIGACT News, 2016

Circuit Complexity of Powering in Fields of Odd Characteristic.

Arkadev Chattopadhyay, Frederic Green, Howard Straubing

Chic. J. Theor. Comput. Sci., 2016

2015

Review of: Incredible Numbers by Ian Stewart.

Frederic Green

SIGACT News, 2015

2013

Review quantum computing since democritus by Scott Aaronson.

Frederic Green

SIGACT News, 2013

2011

In Brute-Force Search of Correlation Bounds for Polynomials.

Frederic Green, Daniel Kreymer, Emanuele Viola

Electron. Colloquium Comput. Complex., 2011

2010

Efficient universal quantum circuits.

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer

Quantum Inf. Comput., 2010

2008

Universal Quantum Circuits.

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer

Electron. Colloquium Comput. Complex., 2008

2007

Review of "Mathematics of Physics and Engineering by Edward K. Blum and Sergey V. Lototsky, " World Scientific.

Frederic Green

SIGACT News, 2007

Small depth quantum circuits.

Debajyoti Bera, Frederic Green, Steven Homer

SIGACT News, 2007

Uniqueness of Optimal Mod 3 Circuits for Parity.

Frederic Green, Amitabha Roy

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

2006

Quantum lower bounds for fanout.

M. Fang, Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang

Quantum Inf. Comput., 2006

2005

Bounds on the Power of Constant-Depth Quantum Circuits.

Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004

The correlation between parity and quadratic polynomials mod 3.

Frederic Green

J. Comput. Syst. Sci., 2004

2002

Counting, fanout and the complexity of quantum ACC.

Frederic Green, Steven Homer, Cristopher Moore, Christopher Pollett

Quantum Inf. Comput., 2002

2001

Relativized separation of EQP from P^NP.

Frederic Green, Randall Pruim

Inf. Process. Lett., 2001

2000

A complex-number Fourier technique for lower bounds on the Mod-m degree.

Frederic Green

Comput. Complex., 2000

On the Complexity of Quantum ACC.

Frederic Green, Steven Homer, Chris Pollett

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

Exponential Sums and Circuits with a Single Threshold Gate and Mod-Gates.

Frederic Green

Theory Comput. Syst., 1999

Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim

Electron. Colloquium Comput. Complex., 1999

Complements of Multivalued Functions.

Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer

Chic. J. Theor. Comput. Sci., 1999

1996

On the Correlation of Symmetric Functions.

Jin-yi Cai, Frederic Green, Thomas Thierauf

Math. Syst. Theory, 1996

1995

A Lower Bound for Monotone Perceptrons.

Frederic Green

Math. Syst. Theory, 1995

The Power of the Middle Bit of a #P Function.

Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, Jacobo Torán

J. Comput. Syst. Sci., 1995

Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate

Frederic Green

Electron. Colloquium Comput. Complex., 1995

Lower Bounds for Depth-Three Circuits With Equals and Mod-Gates.

Frederic Green

Proceedings of the STACS 95, 1995

1993

On the Power of Deterministic Reductions to C=P.

Frederic Green

Math. Syst. Theory, 1993

1992

The Power of the Middle Bit.

Frederic Green, Johannes Köbler, Jacobo Torán

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

An Oracle Separating \oplus P from PP^PH.

Frederic Green

Inf. Process. Lett., 1991

1990

An Oracle Separating +P From PP^ph.

Frederic Green

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1987

NP-Complete Problems in Cellular Automata.

Frederic Green

Complex Syst., 1987