UNC Seal Old Well

 

John H. Halton

Professor of Computer Science


John Halton

Contact Information

Department of Computer Science
University of North Carolina at Chapel Hill
CB #3175, Sitterson Hall, Room 147
Chapel Hill, NC 27599-3175

Home:
108 Carolina Forest
Chapel Hill, NC 27516

(919) 962-1752 (Voice)
(919) 942-6616 (Fax)
(919) 942-4856 (Home)

To send me e-mail, click here: halton at cs.unc.edu


Education


Honors


Research Interests

Applications of combinatorial and probabilistic methods, and scientific and mathematical analysis, to computational, scientific, and engineering problems.

Monte Carlo method. All aspects of the method are studied---including the design and analysis of quasi-random sequences and sets; pseudo-random and quasi-random trees for parallel and branching computations; sampling in multi-dimensional spaces, with generalized probabilities; efficient variance-reduction techniques; generalized antithetic transformations; solution of large linear and nonlinear systems; sequential sampling techniques; parallel- and multi-processing; smooth approximation; optimization; and all kinds of applications.

Combinatorial, probabilistic, geometric, and parallel algorithms. These are designed and analyzed for a variety of problems, such as the Traveling Salesman Problem, application of tree structure to computation, bin-packing, triangulation, and the Shoelace Problem.

Decision-making in applied science and engineering. Mathematical, statistical, and scientific methods are employed.

Mathematics and numerical analysis. Various problems relating to combinatorics, graphs, algebra, analysis, asymptotics, and geometry are investigated.

Absolute and probabilistic bounds on performance of complex systems. These include multicomputer algorithms, questions of scale, networking and communication paradigms, control schemes, debugging strategies, fault-tolerance and error-correction, distributed operating systems, and parallel languages.

PC boards and VLSI chips. The design of efficient layouts, and the efficient process of design of such circuits, are studied and analyzed.


Selected Publications

The shortest path through many points. Proceedings of the Cambridge Philosophical Society, 55 (1959) pp. 299–327 (with J. E. BEARDWOOD and J. M. HAMMERSLEY)

On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numerische Mathematik, 2 (1960) pp. 84–90.

The extreme and L2 discrepancies of some plane sets. Monatshefte für Mathematik, 73 (1969) pp. 316–328 (with S. K. ZAREMBA)

A retrospective and prospective survey of the Monte Carlo method. Society for Industrial and Applied Mathematics (SIAM) Review, 12 (1970) pp. 1–63.

A fast algorithm for the Euclidean Traveling Salesman Problem, optimal with probability one. SIAM Journal on Computing, 11 (1982) pp. 28–46 (with R. TERADA)

On the efficiency of generalized antithetic transformations for Monte Carlo integration. Nuclear Science and Engineering, 98 (1988) pp. 299–316.

Pseudo-random trees—multiple independent sequence generators for parallel and branching computations. Journal of Computational Physics, 84 (1989) pp. 1–56.

The properties of random trees. Information Sciences, 47 (1989) pp. 95–133.

On the thickness of graphs of given degree. Information Sciences, 54 (1991) pp. 219–238.

Sequential Monte Carlo techniques for the solution of linear systems. Journal of Scientific Computing, 9 (1994) pp. 213–257.

Quasi-probability—why quasi-Monte-Carlo methods are statistically valid and how their errors can be estimated statistically. Monte Carlo Methods & Applications, 11 (2005) pp. 203–350.

Sequential Monte Carlo techniques for solving non-linear systems. Monte Carlo Methods & Applications, 12 (2006) pp. 113–141.

Sequential Monte Carlo for linear systems—a practical summary. Monte Carlo Methods & Applications, 14 (2008) pp. 1–27.

Sigma-algebra theorems.  Monte Carlo Methods & Applications, 14 (2008) pp. 171–189.


Click here for a full list of publications.

John H. Halton (halton at cs.unc.edu)
Last updated 12 December 2008


@ To the faculty information page

@To the Computer Science Department home page