# Cristopher Moore

According to our database

Collaborative distances:

^{1}, Cristopher Moore authored at least 95 papers between 1996 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2018

Minimum Circuit Size, Graph Isomorphism, and Related Problems.

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Forkable Strings are Rare.

IACR Cryptology ePrint Archive, 2017

Designing Strassen's algorithm.

Electronic Colloquium on Computational Complexity (ECCC), 2017

The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness.

Bulletin of the EATCS, 2017

Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization.

Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime.

Proceedings of the Approximation, 2017

2016

Codes, lower bounds, and phase transitions in the symmetric rendezvous problem.

Random Struct. Algorithms, 2016

Information-theoretic thresholds for community detection in sparse networks.

Proceedings of the 29th Conference on Learning Theory, 2016

Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering.

Proceedings of the 54th Annual Allerton Conference on Communication, 2016

2015

Optimal ε-Biased Sets with Just a Little Randomness.

SIAM J. Discrete Math., 2015

Approximate Representations, Approximate Homomorphisms, and Low-Dimensional Embeddings of Groups.

SIAM J. Discrete Math., 2015

Group representations that resist random sampling.

Random Struct. Algorithms, 2015

Limitations of single coset states and quantum algorithms for code equivalence.

Quantum Information & Computation, 2015

Graph Isomorphism and Circuit Size.

Electronic Colloquium on Computational Complexity (ECCC), 2015

2014

An Entropic Proof of Chang's Inequality.

SIAM J. Discrete Math., 2014

Group representations that resist random sampling.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Oriented and degree-generated block models: generating and inferring communities with inhomogeneous degree distributions.

J. Complex Networks, 2014

Tree codes and a conjecture on exponential sums.

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

The Complexity of the Fermionant and Immanants of Constant Width [Note].

Theory of Computing, 2013

Scalable text and link analysis with mixed-topic link models.

Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013

The Power of Choice for Random Satisfiability.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

Small-Bias Sets for Nonabelian Groups - Derandomizations of the Alon-Roichman Theorem.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Approximating the Permanent via Nonabelian Determinants.

SIAM J. Comput., 2012

Tight Bounds on the Threshold for Permuted k-Colorability.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

A Graph Integral Formulation of the Circuit Partition Polynomial.

Combinatorics, Probability & Computing, 2011

The Rigidity Transition in Random Graphs.

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Active learning for node classification in assortative and disassortative networks.

Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011

McEliece and Niederreiter Cryptosystems That Resist Quantum Fourier Sampling Attacks.

Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011

Independent Sets in Random Graphs from the Weighted Second Moment Method.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

The Nature of Computation.

Oxford University Press, ISBN: 978-0-19-923321-2, 2011

2010

Finding conjugate stabilizer subgroups in PSL and related groups.

Quantum Information & Computation, 2010

Continuous and Discrete Methods in Computer Science.

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Bounds on the Quantum Satisfiability Threshold.

Proceedings of the Innovations in Computer Science, 2010

Frugal and Truthful Auctions for Vertex Covers, Flows and Cuts.

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Quantum algorithms for Simon's problem over nonabelian groups.

ACM Trans. Algorithms, 2009

2008

A simple constant-probability RP reduction from NP to Parity P.

Electronic Colloquium on Computational Complexity (ECCC), 2008

2007

The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts.

SIAM J. Comput., 2007

For distinguishing conjugate hidden subgroups, the pretty good measurement is as good as it gets.

Quantum Information & Computation, 2007

On the impossibility of a quantum sieve algorithm for graph isomorphism.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Quantum algorithms for Simon's problem over general groups.

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold.

SIAM J. Comput., 2006

MAX

*k*-CUT and approximating the chromatic number of random graphs.
Random Struct. Algorithms, 2006

Limitations of quantum coset states for graph isomorphism.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Global connectivity from local geometric constraints for sensor networks with various wireless footprints.

Proceedings of the Fifth International Conference on Information Processing in Sensor Networks, 2006

Structural Inference of Hierarchies in Networks.

Proceedings of the Statistical Network Analysis: Models, Issues, and New Directions, 2006

2005

On the computational power of probabilistic and quantum branching program.

Inf. Comput., 2005

The resolution complexity of random graph

*k*-colorability.
Discrete Applied Mathematics, 2005

On the bias of traceroute sampling: or, power-law degree distributions in regular graphs.

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

The Symmetric Group Defies Strong Fourier Sampling.

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Fearful Symmetries: Quantum Computing, Factoring, and Graph Isomorphism.

Proceedings of the Algorithms, 2005

A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas.

Proceedings of the Approximation, 2005

Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively.

Proceedings of the Proceedings, 2005

2004

The Resolution Complexity of Random Graph k-Colorability

Electronic Colloquium on Computational Complexity (ECCC), 2004

The power of basis selection in fourier sampling: hidden subgroup problems in affine groups.

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Generic quantum Fourier transforms.

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

From Spin Glasses to Hard Satisfiable Formulas.

Proceedings of the Theory and Applications of Satisfiability Testing, 2004

From Spin Glasses to Hard Satisfiable Formulas.

Proceedings of the SAT 2004, 2004

Sampling Grid Colorings with Fewer Colors.

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Building the Components for a Biomolecular Computer.

Proceedings of the DNA Computing, 10th International Workshop on DNA Computing, 2004

How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails.

Proceedings of the Principles and Practice of Constraint Programming, 2004

Rectangles and Squares Recognized by Two-Dimensional Automata.

Proceedings of the Theory Is Forever, 2004

Counting Connected Graphs and Hypergraphs via the Probabilistic Method.

Proceedings of the Approximation, 2004

The Chromatic Number of Random Regular Graphs.

Proceedings of the Approximation, 2004

Hiding Satisfying Assignments: Two Are Better than One.

Proceedings of the Nineteenth National Conference on Artificial Intelligence, 2004

2003

MAX k-CUT and Approximating the Chromatic Number of Random Graphs.

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002

Counting, fanout and the complexity of quantum ACC.

Quantum Information & Computation, 2002

Ribbon Tile Invariants from the Signed Area.

J. Comb. Theory, Ser. A, 2002

An Analog Characterization of the Grzegorczyk Hierarchy.

J. Complexity, 2002

Quantum and Stochastic Programs of Bounded Width

Electronic Colloquium on Computational Complexity (ECCC), 2002

Almost all graphs with average degree 4 are 3-colorable.

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Tiling groups for Wang tiles.

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Quantum Walks on the Hypercube.

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

On the 2-Colorability of Random Hypergraphs.

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics.

Proceedings of the Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, 2002

Quantum and Stochastic Branching Programs of Bounded Width.

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

The Asymptotic Order of the Random k -SAT Threshold.

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Parallel Quantum Computation and Quantum Codes.

SIAM J. Comput., 2001

Hard Tiling Problems with Simple Tiles.

Discrete & Computational Geometry, 2001

New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata.

Proceedings of the STACS 2001, 2001

The phase transition in 1-in-k SAT and NAE 3-SAT.

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Satisfiability of Systems of Equations over Finite Monoids.

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

An n-Dimensional Generalization of the Rhombus Tiling.

Proceedings of the Discrete Models: Combinatorics, Computation, and Geometry, 2001

2000

Quantum automata and quantum grammars.

Theor. Comput. Sci., 2000

Circuits and Expressions with Nonassociative Gates.

J. Comput. Syst. Sci., 2000

Iteration, Inequalities, and Differentiability in Analog Computers.

J. Complexity, 2000

Upper and Lower Bounds on Continuous-Time Computation.

Proceedings of the Unconventional Models of Computation, 2000

Equation Satisfiability and Program Satisfiability for Finite Monoids.

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999

Closed-for Analytic Maps in One and Two Dimensions can Simulate Universal Turing Machines.

Theor. Comput. Sci., 1999

Quantum Circuits: Fanout, Parity, and Counting

Electronic Colloquium on Computational Complexity (ECCC), 1999

1998

Dynamical Recognizers: Real-Time Language Recognition by Analog Computers.

Theor. Comput. Sci., 1998

1997

Commuting Cellular Automata.

Complex Systems, 1997

Circuits and Expressions with NOn-Associative Gates.

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Recursion Theory on the Reals and Continuous-Time Computation.

Theor. Comput. Sci., 1996

Algebraic Properties of the Block Transformation on Cellular Automata.

Complex Systems, 1996

Life Without Death is P-complete.

Complex Systems, 1996