Jack Lutz is an American theoretical computer scientist best known for developing the concepts of resource-bounded measure [1] and effective dimension; [2] he has also published research on DNA computing and self-assembly. He is a professor of computer science and mathematics at Iowa State University.
Lutz was a student at the University of Kansas, graduating in 1976 and earning master's degrees in mathematics and in computer science there in 1979 and 1981 respectively. [3] He went to the California Institute of Technology for doctoral study in mathematics, and completed his Ph.D. in 1987, with the dissertation Resource-Bounded Category and Measure in Exponential Complexity Classes supervised by Alexander S. Kechris. [3] [4]
He has spent the rest of his career at Iowa State University, as an assistant professor from 1987 to 1992, associate professor from 1992 to 1996, and full professor since 1996. [3] At Iowa State, he directs the Laboratory for Molecular Programming. [5]
Lutz is married to Robyn Lutz, a professor of computer science at Iowa State University; their son Neil Lutz [6] is also a computer scientist and a visiting assistant professor of computer science at Swarthmore College. [7] They have published together on algorithmic game theory in DNA computing. [8]
Complexity characterizes the behavior of a system or model whose components interact in multiple ways and follow local rules, leading to non-linearity, randomness, collective dynamics, hierarchy, and emergence.
Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely. The theory is computably axiomatizable; the axioms include a schema of induction.
Combinatorial game theory measures game complexity in several ways:
Theoretical computer science is a subfield of computer science and mathematics that focuses on the abstract and mathematical foundations of computation.
Linear logic is a substructural logic proposed by French logician Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also been studied for its own sake, more broadly, ideas from linear logic have been influential in fields such as programming languages, game semantics, and quantum physics, as well as linguistics, particularly because of its emphasis on resource-boundedness, duality, and interaction.
Giorgi Japaridze is a Georgian-American researcher in logic and theoretical computer science. He currently holds the title of Full Professor at the Computing Sciences Department of Villanova University. Japaridze is best known for his invention of computability logic, cirquent calculus, and Japaridze's polymodal logic.
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.
In logic and theoretical computer science, and specifically proof theory and computational complexity theory, proof complexity is the field aiming to understand and analyse the computational resources that are required to prove or refute statements. Research in proof complexity is predominantly concerned with proving proof-length lower and upper bounds in various propositional proof systems. For example, among the major challenges of proof complexity is showing that the Frege system, the usual propositional calculus, does not admit polynomial-size proofs of all tautologies. Here the size of the proof is simply the number of symbols in it, and a proof is said to be of polynomial size if it is polynomial in the size of the tautology it proves.
Harlan D. Mills was professor of computer science at the Florida Institute of Technology and founder of Software Engineering Technology, Inc. of Vero Beach, Florida. Mills' contributions to software engineering have had a profound and enduring effect on education and industrial practice. Since earning his Ph.D. in Mathematics at Iowa State University in 1952, Mills led a distinguished career.
Harry George Mairson is a theoretical computer scientist and professor of computer science in the Volen National Center for Complex Systems at Brandeis University in Waltham, Massachusetts. His research is in the fields of logic in computer science, lambda calculus and functional programming, type theory and constructive mathematics, computational complexity theory, and algorithmics.
In mathematics, effective dimension is a modification of Hausdorff dimension and other fractal dimensions that places it in a computability theory setting. There are several variations of which the most common is effective Hausdorff dimension. Dimension, in mathematics, is a particular way of describing the size of an object. Hausdorff dimension generalizes the well-known integer dimensions assigned to points, lines, planes, etc. by allowing one to distinguish between objects of intermediate size between these integer-dimensional objects. For example, fractal subsets of the plane may have intermediate dimension between 1 and 2, as they are "larger" than lines or curves, and yet "smaller" than filled circles or rectangles. Effective dimension modifies Hausdorff dimension by requiring that objects with small effective dimension be not only small but also locatable in a computable sense. As such, objects with large Hausdorff dimension also have large effective dimension, and objects with small effective dimension have small Hausdorff dimension, but an object can have small Hausdorff but large effective dimension. An example is an algorithmically random point on a line, which has Hausdorff dimension 0 but effective dimension 1.
In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form where the variables are interpreted as having real number values, and where is a quantifier-free formula involving equalities and inequalities of real polynomials. A sentence of this form is true if it is possible to find values for all of the variables that, when substituted into formula , make it become true.
Samuel R. (Sam) Buss is an American computer scientist and mathematician who has made major contributions to the fields of mathematical logic, complexity theory and proof complexity. He is currently a professor at the University of California, San Diego, Department of Computer Science and Department of Mathematics.
Toniann Pitassi is a Canadian-American mathematician and computer scientist specializing in computational complexity theory. She is currently Jeffrey L. and Brenda Bleustein Professor of Engineering at Columbia University and was Bell Research Chair at the University of Toronto.
Daniel Mier Gusfield is an American computer scientist, Distinguished Professor of Computer Science at the University of California, Davis. Gusfield is known for his research in combinatorial optimization and computational biology.
Benjamin E. Rossman is an American mathematician and theoretical computer scientist, specializing in computational complexity theory. He is currently an associate professor of computer science and mathematics at Duke University.
Anna Maria Zdunik is a Polish mathematician. She specializes in dynamical systems, and is a professor at the University of Warsaw.
Robyn R. Lutz is an American computer scientist whose research involves software engineering, including modeling and checking software requirements and software system safety. She is a professor of computer science at Iowa State University.
In this survey we present the fundamental results of Lutz's resource-bounded measure theory
We continue the study of effective Hausdorff dimension as it was initiated by Lutz
| International | |
|---|---|
| National | |
| Academics | |
