# Research

## ArXiv E-print Postings

You can find the complete listing of my arXiv postings on my arXiv author page.

## DBLP Home Page

My home page on the DBLP, which lists many of my publications, with hyperlinks.

## Curriculum Vitae

My curriculum vitae, updated January 2013.

## Research Articles

Journal Articles

[2006] | How to Fool an Unbounded Adversary with a Short Key , In Information Theory, IEEE Transactions on, volume 52, 2006. [bib] [pdf] [doi] |

[2015] | Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups , In Communications in Mathematical Physics, 2015. [bib] [doi] |

[2015] | Limitations of Single Coset States and Quantum Algorithms for Code Equivalence , In Quantum Information and Computation, volume 14, 2015. [bib] |

[2015] | Dealing with undependable workers in decentralized network supercomputing , In Theoretical Computer Science, volume 561, Part B, 2015. (Special Issue on Distributed Computing and Networking) [bib] [doi] |

[2014] | Group representations that resist random sampling , In Random Structures and Algorithms, 2014. [bib] [doi] |

[2014] | A One-time Stegosystem and its Application to Efficient Covert Communication , In Journal of Cryptology, volume 27, 2014. [bib] [doi] |

[2014] | An Entropic Proof of Chang's Inequality , In SIAM Journal on Discrete Mathematics, volume 28, 2014. [bib] [doi] |

[2014] | Single Cell Analysis Reveals the Stochastic Phase of Reprogramming to Pluripotency is an Ordered Probabilistic Process , In PLoS ONE, volume 9, 2014. [bib] [doi] |

[2014] | Online Metric Tracking and Smoothing , In Algorithmica, volume 68, 2014. [bib] [doi] |

[2012] | The Time Complexity of A* with Approximate Heuristics on Multiple-Solution Search Spaces , In Journal of AI Research, volume 45, 2012. [bib] |

[2012] | Approximating the Permanent via Nonabelian Determinants , In SIAM J. Comput., volume 41, 2012. [bib] [pdf] [doi] |

[2012] | The one-way communication complexity of subgroup membership , In Chicago Journal of Theoretical Computer Science, volume 2011, 2012. [bib] [doi] |

[2011] | Spectral Concentration of Positive Functions on Compact Groups , In Journal of Fourier Analysis and Applications, Birkhäuser Boston, 2011. [bib] [pdf] [doi] |

[2011] | A Graph Integral Formulation of the Circuit Partition Polynomial , In Combinatorics, Probability & Computing, volume 20, 2011. [bib] [pdf] [doi] |

[2010] | On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism , In SIAM J. Comput., Society for Industrial and Applied Mathematics, volume 39, 2010. [bib] [pdf] [doi] |

[2010] | Limitations of Quantum Coset States for Graph Isomorphism , In J. ACM, ACM, volume 57, 2010. [bib] [pdf] [doi] |

[2010] | Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs , In Quantum Information and Computation, volume 10, 2010. [bib] [pdf] |

[2010] | Finding Conjugate Stabilizer Subgroups in PSL and Related Groups , In Quantum Information and Computation, volume 10, 2010. [bib] [pdf] |

[2009] | State-Wide Elections, Optical Scan Voting Systems, and the Pursuit of Integrity , In Trans. Info. For. Sec., IEEE Press, volume 4, 2009. [bib] [pdf] [doi] |

[2009] | Quantum Algorithms for Simon's Problem Over General Groups , In ACM Trans. Algorithms, ACM, volume 6, 2009. [bib] [pdf] [doi] |

[2008] | The Symmetric Group Defies Strong Fourier Sampling , In SIAM J. Comput., Society for Industrial and Applied Mathematics, volume 37, 2008. [bib] [pdf] [doi] |

[2008] | Reliable Implementation of Real Number Algorithms: Theory and Practice , Chapter in (Peter Hertling, Christoph M. Hoffmann, Wolfram Luther, Nathalie Revol, eds.), Springer-Verlag, 2008. [bib] [pdf] [doi] |

[2008] | Modeling Time and Topology for Animation and Visualization with Examples on Parametric Geometry , In Theor. Comput. Sci., Elsevier Science Publishers Ltd., volume 405, 2008. [bib] [pdf] [doi] |

[2008] | Uncertainty Principles for Compact Groups , In Illinois Journal of Mathematics, volume 52, 2008. [bib] [pdf] |

[2007] | For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets , In Quantum Information and Computation, volume 7, 2007. [bib] [pdf] |

[2007] | The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts , In SIAM J. Comput., Society for Industrial and Applied Mathematics, volume 37, 2007. [bib] [pdf] [doi] |

[2007] | Failure-Sensitive Analysis of Parallel Algorithms with Controlled Memory Access Concurrency , In Parallel Processing Letters, volume 17, 2007. [bib] [pdf] [doi] |

[2006] | Distributed Scheduling for Disconnected Cooperation , In Distributed Computing, Springer Berlin / Heidelberg, volume 18, 2006. [bib] [pdf] [doi] |

[2006] | Generic Quantum Fourier Transforms , In ACM Trans. Algorithms, ACM, volume 2, 2006. [bib] [pdf] [doi] |

[2006] | Computational Topology for Isotopic Surface Reconstruction , In Theor. Comput. Sci., Elsevier Science Publishers Ltd., volume 365, 2006. [bib] [pdf] [doi] |

[2006] | Quantum Random Walk with Rydberg Atoms in an Optical Lattice , In New Journal of Physics, volume 8, 2006. [bib] [pdf] [doi] |

[2005] | Decoherence in Quantum Walks on the Hypercube , In Phys. Rev. A, American Physical Society, volume 72, 2005. [bib] [pdf] [doi] |

[2005] | Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups , In SIAM J. Comput., Society for Industrial and Applied Mathematics, volume 34, 2005. [bib] [pdf] [doi] |

[2005] | The Do-All Problem with Byzantine Processor Failures , In Theor. Comput. Sci., Elsevier Science Publishers Ltd., volume 333, 2005. [bib] [pdf] [doi] |

[2004] | Random Cayley Graphs are Expanders: A Simple Proof of the Alon-Roichman Theorem , In Electronic Journal of Combinatorics, volume 11, 2004. [bib] [pdf] |

[2004] | Classical and Quantum Function Reconstruction via Character Evaluation , In J. Complex., Academic Press, Inc., volume 20, 2004. [bib] [pdf] [doi] |

[2004] | The Chilean Highway Problem , In Theor. Comput. Sci., Elsevier Science Publishers Ltd., volume 326, 2004. [bib] [pdf] [doi] |

[2004] | The Complexity of Synchronous Iterative Do-All with Crashes , In Distrib. Comput., Springer-Verlag, volume 17, 2004. [bib] [pdf] [doi] |

[2004] | Inapproximability Results for Equations over Finite Groups , In Theor. Comput. Sci., Elsevier Science Publishers Ltd., volume 312, 2004. [bib] [pdf] [doi] |

[2003] | Computational Topology: Ambient Isotopic Approximation of 2-Manifolds , In Theor. Comput. Sci., Elsevier Science Publishers Ltd., volume 305, 2003. [bib] [pdf] [doi] |

[2002] | The Complexity of Solving Equations Over Finite Groups , In Inf. Comput., Academic Press, Inc., volume 178, 2002. [bib] [pdf] [doi] |

[2001] | Perfect Information Leader Election in $\log* n + 0(1)$ Rounds , In J. Comput. Syst. Sci., Academic Press, Inc., volume 63, 2001. [bib] [pdf] [doi] |

[2001] | Complexity Bounds on General Hard-Core Predicates , In Journal of Cryptology, Springer New York, volume 14, 2001. [bib] [pdf] [doi] |

[2000] | Alternation in Interaction , In Computational Complexity, Birkhäuser Basel, volume 9, 2000. [bib] [pdf] [doi] |

[2000] | An Easy Reduction of an Isoperimetric Inequality on the Sphere to Extremal Set Theory , In American Mathematical Monthly, 2000. [bib] |

[2000] | Extraction of Optimally Unbiased Bits from a Biased Source , In Information Theory, IEEE Transactions on, volume 46, 2000. [bib] [pdf] [doi] |

[2000] | An Ergodic Theorem for Read-once Non-uniform Deterministic Finite Automata , In Inf. Process. Lett., Elsevier North-Holland, Inc., volume 73, 2000. [bib] [pdf] [doi] |

[1999] | Approximating Latin Square Extensions , In Algorithmica, Springer New York, volume 24, 1999. (10.1007/PL00009274) [bib] [pdf] |

[1998] | A Note on the Asymptotics and Computational Complexity of Graph Distinguishability , In Electronic Journal of Combinatorics, volume 5, 1998. [bib] [pdf] |

[1998] | Symmetric Alternation Captures BPP , In Comput. Complex., Birkhauser Verlag, volume 7, 1998. [bib] [pdf] [doi] |

[1998] | On Embedding Complete Graphs into Hypercubes , In Discrete Math., Elsevier Science Publishers B. V., volume 186, 1998. [bib] [pdf] [doi] |

[1997] | A Note on Optical Routing on Trees , In Inf. Process. Lett., Elsevier North-Holland, Inc., volume 62, 1997. [bib] [pdf] [doi] |

[1995] | Necessary and Sufficient Conditions For Collision-Free Hashing , In Journal of Cryptology, Springer New York, volume 8, 1995. (10.1007/BF00190757) [bib] [pdf] |

[1995] | The Relativized Relationship Between Probabilistically Checkable Debate Systems, IP and PSPACE , In Inf. Process. Lett., Elsevier North-Holland, Inc., volume 53, 1995. [bib] [pdf] [doi] |

[1991] | A Critical Look at Experimental Evaluations of EBL , In Mach. Learn., Kluwer Academic Publishers, volume 6, 1991. [bib] [pdf] [doi] |

Refereed Conference Papers

[2014] | Deterministic Blind Rendezvous in Cognitive Radio Networks , In Proceedings of the 34th International Conference on Distributed Computing Systems (ICDCS), 2014. [bib] |

[2013] | Malicious takeover of voting systems: Arbitrary code execution on optical scan voting terminals , In Proceedings of the 28th Symposium on Applied Computing (SAC 2013), ACM Press, 2013. [bib] |

[2013] | Malicious takeover of voting systems: Arbitrary code execution on optical scan voting terminals , In Proceedings of the 28th Annual ACM Symposium on Applied Computing, SAC '13, ACM, 2013. [bib] [pdf] [doi] |

[2013] | Key-Efficient Steganography with Provable Security Guarantees , In Information Hiding - 14th International Conference, IH 2012, Springer, volume 7692, 2013. [bib] [pdf] |

[2013] | Dealing with Undependable Workers in Decentralized Network Supercomputing , In Proceedings of the 14th International Conference on Distributed Computing and Networking (ICDCN 2013), Springer, volume 7730, 2013. [bib] [doi] |

[2012] | Integrity of Electronic Voting Systems: Fallacious Use of Cryptography , In Proceedings of the 27th Symposium on Applied Computing (SAC 2012), ACM Press, 2012. [bib] |

[2011] | Towards Feasible Implementations of Low-Latency Multi-writer Atomic Registers , In Proceedings of The Tenth IEEE International Symposium on Networking Computing and Applications (NCA 2011), IEEE Computer Society, 2011. [bib] [pdf] [doi] |

[2011] | Data Migration in Heterogeneous Storage Systems , In International Conference on Distributed Computing Systems (ICDCS 2011), IEEE Computer Society, 2011. [bib] [pdf] [doi] |

[2011] | McEliece and Niederreiter Cryptosystems That Resist Quantum Fourier Sampling Attacks , In Advances in Cryptology (CRYPTO 2011) (Phillip Rogaway, ed.), Springer, volume 6841, 2011. [bib] [pdf] [doi] |

[2009] | Taking Total Control of Voting Systems: Firmware Manipulations on an Optical Scan Voting Terminal , In Proceedings of the 2009 ACM symposium on Applied Computing, ACM, 2009. [bib] [pdf] [doi] |

[2008] | Randomized Work-Competitive Scheduling for Cooperative Computing on k-partite Task Graphs , In Proceedings of the 2008 Seventh IEEE International Symposium on Network Computing and Applications, IEEE Computer Society, 2008. [bib] [pdf] [doi] |

[2008] | Pre-Election Testing and Post-Election Audit of Optical Scan Voting Terminal Memory Cards , In Proceedings of the conference on Electronic voting technology, USENIX Association, 2008. [bib] [pdf] |

[2007] | On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism , In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, ACM, 2007. [bib] [pdf] [doi] |

[2007] | On the Value of Good Advice: The Complexity of A* Search with Accurate Heuristics , In Proceedings of the 22nd national conference on Artificial intelligence - Volume 2, AAAI Press, 2007. [bib] [pdf] |

[2007] | Quantum Algorithms for Simon's Problem Over General Groups , In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2007. [bib] [pdf] |

[2006] | Limitations of Quantum Coset States for Graph Isomorphism , In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, ACM, 2006. [bib] [pdf] [doi] |

[2005] | The Symmetric Group Defies Strong Fourier Sampling , In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2005. [bib] [pdf] [doi] |

[2005] | Computational Topology for Reconstruction of Surfaces with Boundary: Integrating Experiments and Theory , In Proceedings of the International Conference on Shape Modeling and Applications 2005, IEEE Computer Society, 2005. [bib] [pdf] [doi] |

[2004] | The Power of Basis Selection in Fourier Sampling: Hidden Subgroup Problems in Affine Groups , In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2004. [bib] [pdf] |

[2004] | Generic Quantum Fourier Transforms , In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2004. [bib] [pdf] |

[2003] | A Note on the Set Systems Used for Broadcast Encryption , In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2003. [bib] [pdf] |

[2003] | Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups , In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM, 2003. [bib] [pdf] [doi] |

[2002] | How to Fool an Unbounded Adversary with a Short Key , In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, Springer-Verlag, 2002. [bib] [pdf] |

[2002] | Optimally Work-Competitive Scheduling for Cooperative Computing with Merging Groups , In Proceedings of the twenty-first annual symposium on Principles of distributed computing, ACM, 2002. [bib] [pdf] [doi] |

[2002] | Inapproximability Results for Equations over Finite Groups , In Proceedings of the 29th International Colloquium on Automata, Languages and Programming, Springer-Verlag, 2002. [bib] [pdf] |

[2001] | Optimal Scheduling for Disconnected Cooperation , In Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, ACM, 2001. [bib] [pdf] [doi] |

[2001] | Local Scheduling for Distributed Cooperation , In Proceedings of the IEEE International Symposium on Network Computing and Applications (NCA'01), IEEE Computer Society, 2001. [bib] [pdf] |

[2001] | The Complexity of Synchronous Iterative Do-All with Crashes , In Proceedings of the 15th International Conference on Distributed Computing, Springer-Verlag, 2001. [bib] [pdf] |

[2000] | Distributed Cooperation During the Absence of Communication , In Proceedings of the 14th International Conference on Distributed Computing, Springer-Verlag, 2000. [bib] [pdf] |

[2000] | Distributed Cooperation in the Absence of Communication , In Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, ACM, 2000. [bib] [pdf] [doi] |

[2000] | Normal Subgroup Reconstruction and Quantum Computation Using Group Representations , In Proceedings of the thirty-second annual ACM symposium on Theory of computing, ACM, 2000. [bib] [pdf] [doi] |

[2000] | Spectral Bounds on General Hard Core Predicates , In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, 2000. [bib] [pdf] |

[1999] | Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model , In Proceedings of the thirty-first annual ACM symposium on Theory of computing, ACM, 1999. [bib] [pdf] [doi] |

[1999] | The Complexity of Solving Equations Over Finite Groups , In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, IEEE Computer Society, 1999. [bib] [pdf] |

[1998] | Perfect Information Leader Election in $\log^* n + O(1)$ Rounds , In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1998. [bib] [pdf] |

[1996] | Approximating Latin Square Extensions , In Proceedings of the Second Annual International Conference on Computing and Combinatorics, Springer-Verlag, 1996. [bib] [pdf] |

[1994] | Efficient Probabilistic Checkable Proofs and Applications to Approximation , In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, ACM, 1994. [bib] [pdf] [doi] |

[1993] | Necessary and Sufficient Conditions For Collision-Free Hashing , In Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, Springer-Verlag, 1993. [bib] [pdf] |

[1993] | Efficient Probabilistically Checkable Proofs and Applications to Approximations , In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, ACM, 1993. [bib] [pdf] [doi] |

Refereed Workshop Papers

[2013] | Small-Bias Sets for Nonabelian Groups: Derandomizations of the Alon-Roichman Theorem , In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Springer, volume 8096, 2013. [bib] [doi] |

[2009] | Automating Voting Terminal Event Log Analysis , In Proceedings of the 2009 conference on Electronic voting technology/workshop on trustworthy elections, USENIX Association, 2009. [bib] [pdf] |

[2008] | Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs , In Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, Springer-Verlag, 2008. [bib] [pdf] [doi] |

[2007] | An Authentication and Ballot Layout Attack Against an Optical Scan Voting Terminal , In Proceedings of the USENIX Workshop on Accurate Electronic Voting Technology, USENIX Association, 2007. [bib] [pdf] |

[2007] | Soft Edge Coloring , In Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer-Verlag, 2007. [bib] [pdf] [doi] |

[2003] | Distributed Cooperation and Adversity: Complexity Trade-offs , In Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge: Paris C. Kanellakis memorial workshop on the occasion of his 50th birthday, ACM, 2003. [bib] [pdf] [doi] |

[2002] | Quantum Walks on the Hypercube , In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, Springer-Verlag, 2002. [bib] [pdf] |

Powered by bibtexbrowser