1
Leonard Adleman
March 2011
ACM Turing award lectures
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 403, Downloads (12 Months): 1,710, Downloads (Overall): 1,931
Full text available:
Mp4
2
The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
Leonard Adleman,
Jarkko Kari,
Lila Kari,
Dustin Reishus,
Petr Sosik
March 2009
SIAM Journal on Computing: Volume 38 Issue 6, February 2009
Publisher: Society for Industrial and Applied Mathematics
Self-assembly, the process by which objects autonomously come together to form complex structures, is omnipresent in the physical world. Recent experiments in self-assembly demonstrate its potential for the parallel creation of a large number of nanostructures, including possibly computers. A systematic study of self-assembly as a mathematical process has been ...
Keywords:
molecular computing, tiling, self-assembly, undecidability, DNA computing
3
On the Decidability of Self-Assembly of Infinite Ribbons
Leonard M. Adleman,
Jarkko Kari,
Lila Kari,
Dustin Reishus
November 2002
FOCS '02: Proceedings of the 43rd Symposium on Foundations of Computer Science
Publisher: IEEE Computer Society
Self-assembly, the process by which objects autonomously come together to form complex structures, is omnipresent in the physical world. A systematic study of self-assembly as a mathematical process has been initiated. The individual components are modelled as square tiles on the infinite two-dimensional plane. Each side of a tile is ...
4
Combinatorial optimization problems in self-assembly
Len Adleman,
Qi Cheng,
Ashish Goel,
Ming-Deh Huang,
David Kempe,
Pablo Moisset de Espanés,
Paul Wilhelm Karl Rothemund
May 2002
STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing
Publisher: ACM
Bibliometrics:
Citation Count: 66
Downloads (6 Weeks): 81, Downloads (12 Months): 99, Downloads (Overall): 1,058
Full text available:
PDF
Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, DNA computation, and amorphous computing. In this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes ...
5
Leonard M. Adleman,
Ming-Deh Huang
September 2001
Journal of Symbolic Computation: Volume 32 Issue 3, 09/01/2001
Publisher: Academic Press, Inc.
We develop efficient methods for deterministic computations with semi-algebraic sets and apply them to the problem of counting points on curves and Abelian varieties over finite fields. For Abelian varieties of dimension g in projective N space overFq, we improve Pila�s result and show that the problem can be solved ...
6
Running time and program size for self-assembled squares
July 2001
STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing
Publisher: ACM
Bibliometrics:
Citation Count: 85
Downloads (6 Weeks): 29, Downloads (12 Months): 124, Downloads (Overall): 568
Full text available:
PDF
Recently Rothemund and Winfree [6] have considered the program size complexity of constructing squares by self-assembly. Here, we consider the time complexity of such constructions using a natural generalization of the Tile Assembly Model defined in [6]. In the generalized model, the Rothemund-Winfree construction of n \times n squares requires ...
7
Solution of a Satisfiability Problem on a Gel-Based DNA Computer
Ravinderjit S. Braich,
Cliff Johnson,
Paul W. K. Rothemund,
Darryl Hwang,
Nickolas V. Chelyapov,
Leonard M. Adleman
June 2000
DNA '00: Revised Papers from the 6th International Workshop on DNA-Based Computers: DNA Computing
Publisher: Springer-Verlag
We have succeeded in solving an instance of a 6-variable 11- clause 3-SAT problem on a gel-based DNA computer. Separations were performed using probes covalently bound to polyacrylamide gel. During the entire computation, DNA was retained within a single gel and moved via electrophoresis. The methods used appear to be ...
8
A subexponential algorithm for discrete logarithms over hyperelliptic curves of large genus over GF (q)
Leonard M. Adleman,
Jonathan DeMarrais,
Ming-Deh Huang
September 1999
Theoretical Computer Science - Special issue: cryptography: Volume 226 Issue 1-2, Sept. 17, 1999
Publisher: Elsevier Science Publishers Ltd.
Keywords:
subexponential algorithms, discrete logarithm, elliptic and hyperelliptic curves
9
Function field sieve method for discrete logarithms over finite fields
Leonard M. Adleman,
Ming-Deh A. Huang
May 1999
Information and Computation: Volume 151 Issue 1-2, May 25, 1999
Publisher: Academic Press, Inc.
10
Function Field Sieve Method for Discrete Logarithms over Finite Fields
Leonard M. Adleman,
Ming-Deh A. Huang
May 1999
Information and Computation: Volume 151 Issue 1, May 1999
Publisher: Academic Press, Inc.
We present a function field sieve method for discrete logarithms over finite fields. This method is an analog of the number field sieve method originally developed for factoring integers. It is asymptotically faster than the previously known algorithms when applied to finite fields Fpn, where p6�n.
11
Quantum Computability
Leonard M. Adleman,
Jonathan DeMarrais,
Ming-Deh A. Huang
October 1997
SIAM Journal on Computing: Volume 26 Issue 5, Oct. 1997
Publisher: Society for Industrial and Applied Mathematics
In this paper some theoretical and (potentially) practical aspects of quantum computing are considered. Using the tools of transcendental number theory it is demonstrated that quantum Turing machines (QTM) with rational amplitudes are sufficient to define the class of bounded error quantum polynomial time (BQP) introduced by Bernstein and Vazirani ...
Keywords:
quantum Turing machines, quantum complexity classes
12
Counting Rational Points on Curves and Abelian Varieties over Finite Fields
May 1996
ANTS-II: Proceedings of the Second International Symposium on Algorithmic Number Theory
Publisher: Springer-Verlag
13
Efficient checkers for number-theoretic computations
Leonard M. Adleman,
Ming-Deh Huang,
Kireeti Kompella
August 1995
Information and Computation: Volume 121 Issue 1, Aug. 15, 1995
Publisher: Academic Press, Inc.
14
L. M. Adleman
November 1994
SFCS '94: Proceedings of the 35th Annual Symposium on Foundations of Computer Science
Publisher: IEEE Computer Society
Though algorithmic number theory is one of man's oldest intellectual pursuits, its current vitality is perhaps unrivalled in history. This is due in part to the injection of new ideas from computational complexity. In this paper, a brief history of the symbiotic relationship between number theory and complexity theory will ...
Keywords:
factoring, algorithmic number theory, computational complexity, open problems, primality testing
15
Molecular computation of solutions to combinatorial problems
Leonard M. Adleman
November 1994
Science: Volume 266 Issue 11, Nov. 1994
Publisher: American Association for the Advancement of Science
16
Open problems in number theoretic complexity, II
Leonard M. Adleman,
Kevin S. McCurley
May 1994
ANTS-I: Proceedings of the First International Symposium on Algorithmic Number Theory
Publisher: Springer-Verlag
17
Leonard M. Adleman,
Ming-Deh A. Huang,
Kireeti Kompella
May 1994
ANTS-I: Proceedings of the First International Symposium on Algorithmic Number Theory
Publisher: Springer-Verlag
18
A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields
Leonard M. Adleman,
Jonathan DeMarrais,
Ming-Deh A. Huang
May 1994
ANTS-I: Proceedings of the First International Symposium on Algorithmic Number Theory
Publisher: Springer-Verlag
19
The function field sieve
Leonard M. Adleman
May 1994
ANTS-I: Proceedings of the First International Symposium on Algorithmic Number Theory
Publisher: Springer-Verlag
20
A subexponential algorithm for discrete logarithms over all finite fields
Leonard M. Adleman,
Jonathan DeMarrais
January 1994
CRYPTO '93: Proceedings of the 13th annual international cryptology conference on Advances in cryptology
Publisher: Springer-Verlag New York, Inc.
usc.edu
Author only
