http:^^www.lcs.mit.edu^web_project^brochure^toc^theory.html

This data set contains WWW-pages collected from computer science departments of various universities

learning that provide better theoretical formulations of
real-world learning situations and the appropriate
algorithms. One example is to learn a concept defined by
Boolean formulae from examples of that concept. Another is
to infer the structure of a finite-state system by
examining the system's input/output behavior. Statistical
techniques are needed to determine how much data are needed
for a given problem; complexity theory helps assess the
difficulty of computing the desired answer from the data.
<p>
Machine-learning research is generally theoretical in
nature (although some is experimental), and involves the
careful specification of models of learning and the precise
specification and analysis of learning algorithms. We use a
wide range of models to capture different aspects of
technical and philosophical relevance, such as learning
from noisy data; learning hierarchically structured
concepts; learning with neural nets; learning via different
output representations; learning to represent a system
containing hidden state variables, and trading off
simplicity of hypothesis with quality of fit to the data.
<p>
<p>
<a name=crypt><center>
<table border>
<tr>
	<td><!WA20><img hspace=6 src=http://www.lcs.mit.edu/web_project/Brochure/toc/goldwasser.gif></td>
	<td width=100 rowspan=2><br></td>
	<td><!WA21><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/micali.gif></td>
	
</tr>
<tr>
<td> <!WA22><A HREF="http://theory.lcs.mit.edu/~shafi"><address><b>Shafrira Goldwasser</b></a>,<br>Professor of <br>Electrical Engineering<br> and  Computer Science<br>(Cryptographic Protocols)</address>
	</td><td> <address><b>Silvio Micali</b></a>,<br>Professor of <br>Electrical Engineering <br> and  Computer Science<br>(Cryptographic Protocols)</address></td>
	
</tr>
</table>
</center>
<p>
<b>Cryptography</b> is another important area of research
within LCS. In its simplest and most ancient form,
cryptography relates to secret communication. Cast in the
framework of complexity theory, the sender, the recipient,
and the adversary are computationally bounded machines. An
encryption system is deemed "secure" when it is
computationally unfeasible for an adversary to obtain
information from their encodings. Since proving non-trivial
lower bounds on the complexity of NP-complete problems is
not within the current state of the art, proof of security
must show that any method for compromising security can be
transformed into an efficient algorithm for a problem (such
as factoring integers) which is generally believed to be
intractable.
<p>
Achieving privacy is only one area of cryptography
research. Another is the design of protocols for
authentication, certified electronic mail, and contract
signing between two or more mutually suspicious parties. In
general, the goal is to perform an arbitrary distributed
computation among many processors, each containing some
portion of the input. Each processor is connected in a
network such that no processor reveals any information
other than that which is intended.
<p>
Protocol research has led to a complexity theory of the
amount of knowledge that must be released in order for one
processor to prove a fact to another processor -- the
theory of "zero-knowledge proofs." Generating pseudo-random
numbers and functions is another important field.
(Randomness is here defined with respect to a specific
model of computation and a specific level of computational
resources.)
<p>
LCS researchers have contributed to virtually all
cryptographic inventions of the past decade, including the
invention of the first public-key cryptosystem,
probabilistic cryptosystems, and the invention of
zero-knowledge proofs.
<p>
<p>
<a name=cc><center>
<table border>
<tr>
	<td><!WA23><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/sipser.gif></td>
	<td width=100 rowspan=2><br></td>
	<td><!WA24><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/karchmer.gif></td>
	
</tr>
<tr>
<td> <address><b>Michael Sipser,</b><br>Professor of Applied Mathematics<br>(Computational Complexity Theory)</address>
	</td><td> <address><b>Mauricio Karchmer</b>,<br>Assistant Professor of Mathematics<br>(Computational Complexity Theory)</address></td>
	
</tr>
</table>
</center>
<p>
LCS also enjoys a traditional leadership role in
<b>computation complexity theory</b>. One of the prime goals
in this field is to devise and study natural schemes for
classifying problems according to their computational
difficulty, then place familiar and important problems
within the appropriate scheme.
<p>
One familiar example is the problem of factoring large
integers -- that is, finding all the prime numbers that
divide the integer evenly. The exercise is not only
theoretically interesting, but also is relevant to
cryptography. The "brute force" method of searching for
prime factors one by one is too slow to be useful. While
better algorithms are known, determining the intrinsic
difficulty of the factoring problem is one of complexity
theory's many exciting questions.
<p>
LCS researchers were the first to show that there are
problems of high intrinsic complexity. Now we are
investigating the complexity of problems akin to factoring
by studying the power of weak computational models, such as
branching programs and monotone circuits of bounded depth.
These formally constrained models are easier to analyze and
thus may help us better understand the standard models. In
closely related work, we are studying the power of
probabilistic computation, parallelism, randomness and
pseudo-randomness, interactive proof systems, and other
basic computing concepts.
<p>
<center>
<table border>
<tr>
	<td><!WA25><img hspace=8 src=http://www.lcs.mit.edu/web_project/Brochure/toc/meyer.gif></td>
	<td width=100 rowspan=2><br></td>
	<td><!WA26><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/elias.gif></td>
	
</tr>
<tr>
<td> <!WA27><A HREF="http://theory.lcs.mit.edu/~meyer"><address><b>Albert R. Meyer,</b></a><br>Hitachi America Professor <br>of Engineering<br>(Program Semantics and Logic)</address>
	</td><td> <address><b>Peter Elias</b>,<br>Professor <b> Emeritus</b><br>and Senior Lecturer<br>(Information Theory)<address></td>
	
</tr>
</table>
</center>
<p>
Elsewhere within LCS, researchers into the <a name=psem><b>theory of
programming semantics and logic</b> aim to provide clear
mathematical foundations and reliable reasoning principles
that conform to the robust functional metaphor programmers
use to design, describe, and justify their programs.
Programming routinely unites high abstraction and pragmatic
design and includes the declaration of procedures,
functions, data types, processes, and "objects." The
researchers' objective is to lay a solid foundation for
this task.
<p>
Computer scientists' notion of a "function," however, may
depend on when and in what context it is evaluated. That
contrasts with the mathematician's classical notion of a
function. Bridging this conceptual gap involves elements of
algebra, modal and intuitionistic logic, and category-,
complexity-, computability-, proof-, and type theory -- all
applied to programming-language design, compiler
construction, and program optimization. This work is being
extended to the study of specifying the meaning and
verification of the properties of parallel and distributed
processes.
<p>
<center>
<table border>
<tr>
	<td><!WA28><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/lynch.gif></td>
	<td width=100 rowspan=2><br></td>
	<td><!WA29><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/awerbuch.gif></td>
	
</tr>
<tr>
<td><!WA30><A HREF="http://theory.lcs.mit.edu/~lynch"><address><b>Nancy Lynch,</b></a><br>Professor of Electrical Engineering <br>and Computer Science<br>(Distributed Computing)</address>
	</td><td> <address><b>Baruch Awerbuch</b>,<br>Research Scientist<br>(Distributed Computing)</address></td>
	
</tr>
</table>
</center>
<p>
<!WA31><a name=tds><A HREF="http://theory.lcs.mit.edu/tds">Distributed computation theory</a> is designed to clarify
the basic capabilities and limitations of concurrent and
distributed computing systems. Research results include new
algorithms and their analysis, impossibility results,
formal concurrent-systems models, and models and techniques
for proving correctness of concurrent algorithms. Problems
typically include getting the non-failing processors to
agree, synchronizing non-failing processors, fault-tolerant
compiling and routing, resource allocation, sharing access
to data, and graph-theoretic problems such as doing a
breadth-first search or finding minimum-cost spanning
trees.
<p>
A basic problem in fault-tolerant computing is to cause
processors to agree among themselves (about the value of a
data item, say, or about a common course of action). While
this is a simple exercise in the absence of faults, it may
be impossible when faults are present: Individual
processors do not have reliable knowledge about the states
of other processors. Our work has led to many interesting
algorithms and impossibility results that demonstrate
conditions under which consensus can or cannot be achieved.
<p>
An important LCS project related to network protocols has
been the development of a series of efficient algorithmic
transformers. The result of this project is the
"compilation" of protocols that were designed for a
relatively simple network model into protocols that run in
a more complex, but more realistic, environment.
<p>
LCS has developed an important formalism -- the
Input/Output Automaton Model, a basic mathematical model
for concurrent and distributed systems and their
components. This simple-state machine model helps describe
interactions between a concurrent system and its
environment. The model not only verifies the correctness of
algorithms but also helps find and fix serious gaps in some
basic existing algorithms -- the construction of
multi-writer atomic registers, for example.

</BODY>
<p>
<!WA32><a href="http://www.lcs.mit.edu/web_project/Brochure/contents.html"><!WA33><img align=left src=http://www.lcs.mit.edu/web_project/Brochure/icons/contents_motif.gif></a>
<!WA34><a href="http://www.lcs.mit.edu/web_project/Brochure/sct/sct.html"><!WA35><img align=left src=http://www.lcs.mit.edu/web_project/Brochure/icons/previous_group_motif.gif></a>
<!WA36><a href="http://www.lcs.mit.edu/web_project/Brochure/hq/hq.html"><!WA37><img align=left src=http://www.lcs.mit.edu/web_project/Brochure/icons/next_motif.gif></a>
</HTML>