35 citations · 103 across the 9 of their papers we have counts for
9 papers
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas
Cristopher Moore, Gabriel Istrate, Demetrios Demopoulos +1
We compute the probability of satisfiability of a class of random Horn-SAT formulae, motivated by a connection with the nonemptiness problem of finite tree automata. In particular,…
Explicit Multiregister Measurements for Hidden Subgroup Problems
Cristopher Moore, Alexander Russell
We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This en…
Hiding Satisfying Assignments: Two are Better than One
Dimitris Achlioptas, Haixia Jia, Cristopher Moore
The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-…
The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
Cristopher Moore, Daniel Rockmore, Alexander Russell +1
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a Hidden Subgroup problem, in which an unknown subgroup H of a g…
On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs
Dimitris Achlioptas, Aaron Clauset, David Kempe +1
Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtainin…
For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
Cristopher Moore, Alexander Russell
Recently Bacon, Childs and van Dam showed that the ``pretty good measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral group D_n in the case where the hidd…