R. Lipton and K. Regan and A. Rudra, ``Simulating Special but Natural Quantum Circuits,'' December 2011. PDF file.
M. Jansen and K. Regan, ``{\,}`Resistant' Polynomials and Stronger Lower Bounds for Depth-Three Arithmetical Formulas,'' in the proceedings of COCOON'07, Springer LNCS 4598, 2007, pp 470--481. PS file PDF file
M. Jansen and K. Regan, ``A Non-Linear Lower Bound for Constant Depth Arithmetical Circuits via the Discrete Uncertainty Principle,'' submitted to Theoretical Computer Science. PS file PDF file
M. Jansen and K. Regan ``On Determinants of Constrained Random Fourier Minors,'' submitted to the Journal of Fourier Analysis and Applications. PDF file
Maurice J. Jansen's 2006 PhD Thesis: PS file PDF file
H. Liu and K.~Regan, ``Improved construction for universality of determinant and permanent,'' {\em Information Processing Letters\/} {\bf 100} (Issue 6, 31 Dec. 2006), 233--237. PS file PDF file
K. Regan, ``Understanding the Mulmuley-Sohoni Approach to P vs. NP,'' Bulletin of the European Association for Theoretical Computer Science 78, October 2002, pp86--97. Invited contribution to Lance Fortnow's Computational Complexity Column. (Fixes some typos in BEATCS published version; dual-listed under "Surveys" below, but also has one original slight strengthening of a lemma in their paper.) PS file PDF file
D.X. Charles and K. Regan, ``On arithmetical formulas whose Jacobians are Groebner Bases,'' accepted subject to revisions to the {\em Journal of Symbolic Logic\/}, 2004. PS file PDF file
K. Regan, ``Polynomial vicinity circuits and nonlinear lower bounds,'' {\em in\/} ``Proceedings, 12th Annual IEEE Conference on Computational Complexity'' Ulm, Germany, June 1997,'' IEEE Computer Science Press, Los Alamitos, CA, 1997, pp~61--68. PS file PDF file
K.~Regan, ``On Super-Linear Lower Bounds in Complexity Theory'' {\em in\/} ``Proceedings, 1995 IEEE Conference on Structure in Complexity Theory, Minneapolis, MN, June 1995,'' pp 50--64. (Mostly a survey---not refereed---invited PC member contribution.) PS file PDF file
J.-Y. Cai, R. Lipton, L. Longpr{\'e}, M. Ogihara, K. Regan, and D. Sivakumar, ``Communication complexity of key agreement on small ranges,'' {\em in\/} ``Proceedings, 11th Annual Symposium on Theoretical Aspects of Computation, Munich, Germany, February 1995,'' Lecture Notes in Computer Science series, Springer Verlag, 1995. PS file PDF file
K. Regan, ``Linear time and memory-efficient computation,'' {\em SIAM Journal on Computing\/} {\bf 25} (1996) 133--168. PS file PDF file
A. Naik, K. Regan, and D. Sivakumar, ``On quasilinear time complexity theory,'' {\em Theoretical Computer Science\/} {\bf 148} (1995) 325--349. PF file PDF file
K. Regan and J. Wang, ``The Quasilinear Isomorphism Challenge,'' {\em SIGACT News\/} {\bf 25}, September 1994, pages 106--113. (not refereed) PS file PDF file
K. Regan, ``A new parallel vector model, with exact characterizations of NC$^k$.'' {\it in\/} ``Proceedings, 11th Annual Symposium on Theoretical Aspects of Computation, Caen, France, February 1994.'' Lecture Notes in Computer Science {\bf 778}, Springer Verlag, 1994, pp 289--300. PS file PDF file
K. Regan, ``Linear time algorithms in memory hierarchies,'' {\em in\/} ``Proceedings, 13th IFIP World Computer Congress, Hamburg, Germany, Aug.-Sep.\ 1994, Volume 1: Technology and Foundations,'' B. Pehrson and I. Simon, eds., {\em IFIP Transactions\/}, Ser. A-51, North-Holland, 1994, pp 609--614. PS file PDF file
K. Regan, ``Linear speed-up, information vicinity, and finite-state machines,'' {\em in\/} ``Proceedings, 13th IFIP World Computer Congress, Hamburg, Germany, Aug.-Sep.\ 1994, Volume 1: Technology and Foundations,'' B. Pehrson and I. Simon, eds., {\em IFIP Transactions\/}, Ser. A-51, North-Holland, 1994, pp 609--614. PS file PDF file
K.~Regan and D.~Sivakumar, ``Probabilistic martingales and BPTIME classes,'' {\em in\/} ``Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, NY, June 1998,'' IEEE Computer Science Press, Los Alamitos, CA, 1998, pp~186--200. PS file PDF file
K.~Regan, D.~Sivakumar, and J.-Y.~Cai, ``Pseudorandom number generators, measure theory, and natural proofs,'' {\em in\/} ``Proceedings, 36th Ann.\ IEEE Symposium on Foundations of Computer Science, Milwaukee, WI, October 1995,'' IEEE Computer Science Press, Los Alamitos, CA, 1995, pp~26--35. PS file PDF file
H. Buhrman, D. van Melkebeek, K. Regan, D. Sivakumar, and M. Strauss, ``A generalization of resource bounded measure, with application to the BPP vs.\ EXP problem,'' {\it SIAM Journal on Computing\/} {\bf 30}, 2001, 576--610. PS file PDF file
R. Downey, M. Fellows, and K. Regan, ``Parameterized Circuit Complexity and the W Hierarchy,'' {\em Theoretical Computer Science\/} {\bf 191}, 1998, 97--115. PS file PDF file
R. Downey, M. Fellows, and K. Regan, Descriptive Complexity and the W. Hierarchy, {\it in\/} P. Beame and S. Buss, eds., ``Proof Complexity and Feasible Arithmetics: Proceedings of a DIMACS Workshop, April 1996,'' volume 39 of the DIMACS Series on Discrete Mathematics and Theoretical Computer Science (Providence:\ AMS), 1997, pages 119--134. PS file PDF file
R. Lipton, K. Regan, and A. Rudra, ``Symmetric Functions Capture General Functio ns,'' to appear in the proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science, Warsaw, Poland, Aug.\ 22--26, 2011 . PS file PDF file
K. Regan and H. Vollmer, ``Gap-Languages and Log-Time Complexity Classes,'' {\em Theoretical Computer Science\/} {\bf 188}, 1998, 101--116. PS file PDF file
F. Green, J. K{\"o}bler, K. Regan, T. Schwentick, and J. Tor{\'a}n, ``The power of the middle bit of a \#P function,'' {\em Journal of Computer and Systems Sciences\/} {\bf 50} (1995) 456--467. PS file PDF file
K. Regan and J. Royer, ``On closure properties of bounded 2-sided error complexity classes.'' {\em Mathematical Systems Theory\/} {\bf 28}, 1995, 229--243. PS file PDF file
M. Crasmaru and C. Glasser and K. Regan and S. Sengupta, ``A protocol for serializing unique strategies,'' MFCS'04 PS file PDF file
S.~Aida and M.~Crasmaru and K.~Regan and O.~Watanabe, ``Games with Uniqueness Properties,'' Theoretical Computer Science 37 (2004), 29--47. PS file PDF file
S.~Kalyanasundaram, R.~Lipton, K.~Regan, and F.~Shokrieh, ``Improved Simulation of Nondeterministic Turing Machines,'' {\em Theoretical Computer Science\/}, to appear in special issue for the MFCS 2010 conference. PDF file
G. DiFatta, G. Haworth, and K. Regan, ``Skill Rating by Bayesian Inference,'' in the proceedings of the 2009 IEEE Symposium on Computational Intelligence and Data Mining (CIDM'09), Nashville, TN, March 30--April 2, 2009, IEEE, pp 89--94. PDF file.
G. Haworth, K. Regan, and G. DiFatta, ``Performance and Prediction: Bayesian Modelling of Fallible Choice in Chess,'' in the proceedings of the 12th ICGA Conference on Advances in Computer Games, Pamplona, Spain, May 11--13, 2009, Final publication version (March 2010), Springer LNCS {\bf 6048}, 2010, pp~99--110. PDF file.
K. Regan and G. Haworth, ``Intrinsic Chess Ratings.'' Proceedings of AAAI 2011. PDF file.
K. Regan, B. Macieja and G. Haworth, ``Understanding Distributions of Chess Performances,'' PDF file of 12/21/11 To appear in the proceedings of the 13th ICGA conference on Advances in Computer Games, Tilburg, Netherlands, November 2011.
K. Regan, ``Intrinsic Ratings Compendium'' draft paper. Gives "IPRs" of tournaments, matches, and individual player peformances, including many pre-1971 historical performance rating estimates. To be updated following a phenomenon recently discovered here that enabled a sizable improvement in the methodology. On large scale this appears to change tournaments by 10--20 points at most, but individual player performances are more volatile. Not rocket science yet...
K. Regan and T. Biswas, ``Psychometric Modeling of Decision Making Via Game Play'' draft paper. Includes the world championship match table from the "Compendium" with Anand-Gelfand 2013 added. Detailed comparison of the fitting methods proposed will await the current expansion of the model to have a depth "d" parameter, whereupon the intrinsic-rating figures will change but expectedly (hopefully) not by much.
A. Jagota and K. Regan, ``Performance of Neural-Net Heuristics for Maximum Clique on Diverse Highly-Compressible Graphs,'' {\em Journal of Global Optimization\/} {\bf 10}, 1997, 439--465. PS file PDF file
A. Jagota, G. Narasimhan, and K. Regan, ``Information capacity of binary weights associative memories,'' {\em Neurocomputing\/} {\bf 19}, 1998, 35--58. PS file PDF file
B.~Postow, K.~Regan, and C.~Smith, ``UPSILON: Universal programming system with incomplete lazy object notation,'' {\em Fundamenta Informaticae\/} {\bf 50}, 2002, 325--359. PS file PDF file
K. Regan, ``Understanding the Mulmuley-Sohoni Approach to P vs. NP,'' Bulletin of the European Association for Theoretical Computer Science 78, October 2002, pp86--97. Invited contribution to Lance Fortnow's Computational Complexity Column. (Fixes some typos in BEATCS published version; dual-listed under "Surveys" below, but also has one original slight strengthening of a lemma in their paper.) PS file PDF file
Polynomials and Combinatorial Definitions of Languages, in L. Hemaspaandra and A. Selman, eds., {\it Complexity Theory Retrospective II\/}, (Berlin and New York: Springer Verlag, 1997), pp 261-293. PS file PDF file
K. Regan, ``Machine models and linear time complexity,'' {\em SIGACT News\/} {\bf 24}, October 1993, pages 5--15. Guest Column for L. Hemaspaandra, ed., ``Complexity Theory Column.'' PS file PDF file
E.~Allender, M.~Loui, and K.~Regan, three chapters for the
{\it CRC Handbook on Algorithms and Theory of Computation\/}
(M.J. Atallah, ed.), (Boca Raton: CRC Press, 1998).
``Chapter 27: Complexity Classes,''
PS file
PDF file
2-column PDF file
``Chapter 28: Reducibility and Completeness,''
PS file
PDF file
2-column PDF file
``Chapter 29: Other Complexity Classes and Measures.''
PS file
PDF file
2-column PDF file
K.W. Regan, ``The topology of provability in complexity theory,'' {\em Journal of Computer and Systems Sciences} {\bf 36}, No. 3 (June 1988) 384-432.
K. Regan, ``Diagonalization, uniformity, and fixed-point theorems,'' {\em Information and Computation\/} {\bf 98} (May 1992), 1--40.
K. Regan, ``Minimum-complexity pairing functions,'' {\em Journal of Computer and Systems Sciences\/} {\bf 45} (Dec. 1992), 385--395.
K. Regan and A. Chakrabarti, ``Quantum Circuits, Polynomials, and Entanglement Measures.'' Partial draft---doesn't have the entanglement measures yet. PDF file.
M. Jansen and K. Regan, ``Orbits and arithmetical circuit lower bounds,'' was submitted to ICALP'04, not all subsumed by later work. PS file PDF file
D.~Charles and K.~Regan, ``Branching Programs With Variables, and Implications for Time-Space Tradeoffs,'' extended abstract withdrawn after a fatal counting error found by a FOCS'01 referee and by another: ``\theta'' in Lemma 4.3 needs to be arbitrarily small /in relation to/ ``\sigma'', not just scaling with \sigma. A fix attempt must involve the space bound, but this is problematic. Still, the idea to greatly strengthen a result by Ajtai may find other legs... PS file PDF file
M.~Ogihara and K.~Regan and S.~Toda, ``Graded Self-Reducibility.'' PS file PDF file
M.~Ogihara and K.~Regan, ``Random Polynomial Time Computable Functions,'' PDF file. Original December 1993 version was submitted to the Complexity 1994 conference.