R. Lipton and K. Regan and A. Rudra, ``Simulating Special but Natural Quantum Circuits,'' December 2011. PDF file.
K. Regan and A. Chakrabarti and C. Guan, ``Algebraic and Logical Emulations of Quantum Circuits,'' Transactions on Computational Science Vol. XXXI (LNCS 10730, 2018), 41--76. Online version, copyright Springer-Verlag. PDF Manuscript.
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.~Fagin, J.~Lenchner, K.~Regan, and N.~Vyas, ``Multi-Structural Games and Number of Quantifiers,'' Proceedings of the ACM/IEEE Symposium on Logic in Computer Science, Rome, June 2021, pages 1--13. Revised version to appear in the journal {\em Logical Methods in Computer Science}, 2024. ArXiv version.
R. Sur\'owka and K. Regan, ``Languages in AC^1 Defined by Iterating Finite Transducers'', to appear in the proceedings of the 2013 University of Krakow PhD Student Research Conference. PDF file
R. Lipton, K. Regan, and A. Rudra, ``Symmetric Functions Capture General Functions,'' 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. Submitted version formatted in larger type. Copyright for the final version is held by AAAI.
K. Regan, B. Macieja and G. Haworth, ``Understanding Distributions of Chess Performances,'' PDF file of 12/21/11 Proceedings of the 13th ICGA conference on Advances in Computer Games, Tilburg, Netherlands, November 2011. Copyright for the final version is held by Springer-Verlag.
K. Regan and T. Biswas, ``Psychometric Modeling of Decision Making Via Game Play,'' working/accepted version to the 2013 IEEE Conference on Computational Intelligence in Games PDF file. Copyright for the final version is held by IEEE.
T. Biswas and K. Regan, ``Efficient Memoization For Approximate Function Evaluation Over Sequence Arguments,'' in the proceedings of the 2014 Conference on Algorithmic Aspects of Information Management (AAIM 2014), Vancouver, Canada, July 2014. PDF file.
K. Regan and T. Biswas and J. Zhou, ``Human and Computer Preferences at Chess,'' in the proceedings of the 8th Multidisciplinary Workshop on Advances in Preference Handling (MPREFS 2014), associated to AAAI 2014, Quebec City, July 2014. PDF file.
T. Biswas and K.~Regan, ``Quantifying Depth and Complexity of Thinking and Knowledge,'' to appear in the proceedings of the 7th International Conference on Agents and Artificial Intelligence (ICAART 2015), Lisbon, Portugal, Jan.\ 10--12, 2015. PDF file.
T. Biswas, G. Haworth, and K. Regan, ``A Comparative Review of Skill Assessment: Performance, Prediction and Profiling,'' in the proceedings of the 14th Advances in Computer Games conference, Leiden, Netherlands, July 2015. PDF file.
T. Biswas and K.~Regan, ``Measuring Level-K Reasoning, Satisficing, and Human Error in Game-Play Data,'' July 2015, accepted to ICMLA 2015. PDF file.
K. Regan, ``Rating Computer Science Via Chess,'' invited submission accepted in final form to the Springer LNCS 10,000 anniversary volume, 2018. PDF file.
K. Regan, "Intrinsic Ratings Compendium", 2012 MS. PDF file, still awaiting major update.
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
R.~Fathi, J.~Teresco, and K.~Regan, ``Measuring Learners' Cognitive Load when Engaged with an Algorithm Visualization Tool,'' {\em Journal of Information Systems Applied Research\/} {\bf 16}, 2023, 58--78. 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. PDF
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.