Publications by Samuel Kutin

• with Daniel Kane, Quantum interpolation of polynomials, journal version in preparation.
  • Presented at CGAC 2010 in honor of Laszlo Babai's 60th birthday.
• with David Petrie Moulton and Lawren Smithline, Computation at a distance. Chicago Journal of Theoretical Computer Science, 2007.
  • An earlier version is available at quant-ph/0701194.
• Quantum lower bound for the collision problem with small range. Theory of Computing, vol. 1 (April, 2005), 29-36.
  • An earlier version is available at quant-ph/0304162.
• with Claire Kenyon, Sensitivity, block sensitivity, and l-block sensitivity. Information and Computation, vol. 189, no. 1 (February, 2004), 43-53.
  • An earlier version is available as University of Chicago Tech Report TR-2001-22.
• with Thomas Hayes and Dieter van Melkebeek, The quantum black-box complexity of majority. Algorithmica, vol. 34, no. 4 (December, 2002), 480-501.
  • An updated version is available at quant-ph/0109101.
• Constructing large set systems with restricted intersections modulo composite numbers. Combinatorics, Probability, and Computing, vol. 11, no. 5 (September, 2002), 475-486.
• with Partha Niyogi, Almost-everywhere algorithmic stability and generalization error. UAI-2002: Uncertainty in Artificial Intelligence (August, 2002, Edmonton)
  • The slides from the poster presentation are available in postscript and pdf.
• with Laszlo Babai, Peter Frankl, and Daniel Stefankovic, Set systems with restricted intersections modulo prime powers. Journal of Combinatorial Theory, Series A, vol. 95, no. 1 (July, 2001), 39-73.
  • You can download the paper.

Thesis

• Algorithmic stability and ensemble-based learning (University of Chicago Ph.D. thesis, June, 2002)

To Appear

• October 2001, with Partha Niyogi: The interaction of stability and weakness in AdaBoost (University of Chicago Tech Report TR-2001-30) (to appear in the Journal of Machine Learning Research)

Technical Reports

• September 2006: Shor's algorithm on a nearest-neighbor machine (quant-ph/0609001)
  • Presented at AQIS 2007.
• October 2004, with Steven Cuccaro, Thomas Draper, and David Petrie Moulton: A new quantum ripple-carry addition circuit (quant-ph/0410184)
  • Presented at QIP 2005.
• June 2004, with Thomas Draper, Eric Rains, and Krysta Svore: A logarithmic-depth quantum carry-lookahead adder (quant-ph/0406142)
  • Presented at EQIS 2004.
• April 2002: Extensions to McDiarmid's inequality when differences are bounded with high probability (University of Chicago Tech Report TR-2002-04)
• March 2002, with Partha Niyogi: Almost-everywhere algorithmic stability and generalization error (University of Chicago Tech Report TR-2002-03)

Other

• Open Spaces. A freeware System 7 mac utility I wrote in 1993. The program was included in Levitus and Brown's Customizing your Mac for Fun and Productivity, on the productivity side.