Cristopher Moore
According to our database^{1},
Cristopher Moore
authored at least 96 papers
between 1996 and 2018.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at orcid.org

at id.loc.gov

at dnb.info
On csauthors.net:
Bibliography
2018
Special Section on the FiftySixth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015).
SIAM J. Comput., 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
Informationtheoretic 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
Informationtheoretic thresholds for community detection in sparse networks.
Proceedings of the 29th Conference on Learning Theory, 2016
Phase transitions and optimal algorithms in highdimensional 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 LowDimensional 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 degreegenerated 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 mixedtopic 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
SmallBias Sets for Nonabelian Groups  Derandomizations of the AlonRoichman 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 kColorability.
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 TwentySecond Annual ACMSIAM 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: 9780199233212, 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 constantprobability 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 ACMSIAM Symposium on Discrete Algorithms, 2007
2006
Random kSAT: Two Moments Suffice to Cross a Sharp Threshold.
SIAM J. Comput., 2006
MAX kCUT 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 kcolorability.
Discrete Applied Mathematics, 2005
On the bias of traceroute sampling: or, powerlaw 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 ContinuousDiscontinuous SecondOrder Transition in the Satisfiability of Random HornSAT 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 kColorability
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 ACMSIAM Symposium on Discrete Algorithms, 2004
Generic quantum Fourier transforms.
Proceedings of the Fifteenth Annual ACMSIAM 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 TwoDimensional 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 kCUT 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 3colorable.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Tiling groups for Wang tiles.
Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2002
Quantum Walks on the Hypercube.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002
On the 2Colorability 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 Nondeterministic TwoDimensional FiniteState Automata.
Proceedings of the STACS 2001, 2001
The phase transition in 1ink SAT and NAE 3SAT.
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 nDimensional 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 ContinuousTime 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
Closedfor 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: RealTime Language Recognition by Analog Computers.
Theor. Comput. Sci., 1998
1997
Commuting Cellular Automata.
Complex Systems, 1997
Circuits and Expressions with NOnAssociative Gates.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997
1996
Recursion Theory on the Reals and ContinuousTime Computation.
Theor. Comput. Sci., 1996
Algebraic Properties of the Block Transformation on Cellular Automata.
Complex Systems, 1996
Life Without Death is Pcomplete.
Complex Systems, 1996