A long standing open problem in the computational complexity theory
is to separate NE from BPP, which is a subclass of $NP_T (NP\cap P/poly)$.
In this paper, we show that $NE\not\subseteq NP_T (NP \cap$ Nonexponentially-Dense-Class),
where Nonexponentially-Dense-Class is the class of languages A without exponential density
(for ... more >>>

We settle a number of questions in variants of Winfree's abstract Tile Assembly Model (aTAM), a model of molecular algorithmic self-assembly. In the "hierarchical" aTAM, two assemblies, both consisting of multiple tiles, are allowed to aggregate together, whereas in the "seeded" aTAM, tiles attach one at a time to a ... more >>>

In this paper we investigate the question whether a perfect matching can be isolated by a weighting scheme
using Chinese Remainder Theorem (short: CRT). We give a systematical analysis to a method based on CRT
suggested by Agrawal in a CCC'03-paper
for testing perfect matchings. We show that ... more >>>