The main SciRate homepage is down (when not logged in). We are working to fix it. See https://github.com/scirate/scirate/issues/337 for updates.

- arXiv.org
- Popular Physics
- Data Analysis, Statistics and Probability
- Space Physics
- Biological Physics
- Optics
- Fluid Dynamics
- Atomic and Molecular Clusters
- General Physics
- Physics and Society
- History and Philosophy of Physics
- Atomic Physics
- Plasma Physics
- Medical Physics
- Geophysics
- Instrumentation and Detectors
- Physics Education
- Chemical Physics
- Computational Physics
- Accelerator Physics
- Classical Physics
- Atmospheric and Oceanic Physics

- Analysis of PDEs
- Number Theory
- Information Theory
- Statistics Theory
- History and Overview
- Mathematical Physics
- Algebraic Geometry
- Representation Theory
- Combinatorics
- Probability
- Group Theory
- Operator Algebras
- Complex Variables
- Symplectic Geometry
- Metric Geometry
- Numerical Analysis
- Optimization and Control
- Differential Geometry
- Dynamical Systems
- Quantum Algebra
- Logic
- Geometric Topology
- General Topology
- General Mathematics
- Functional Analysis
- Rings and Algebras
- Category Theory
- Commutative Algebra
- K-Theory and Homology
- Spectral Theory
- Classical Analysis and ODEs
- Algebraic Topology

- Symbolic Computation
- Information Theory
- Computational Engineering, Finance, and Science
- General Literature
- Formal Languages and Automata Theory
- Information Retrieval
- Multiagent Systems
- Learning
- Neural and Evolutionary Computing
- Computer Vision and Pattern Recognition
- Databases
- Software Engineering
- Programming Languages
- Social and Information Networks
- Sound
- Emerging Technologies
- Numerical Analysis
- Other Computer Science
- Operating Systems
- Artificial Intelligence
- Distributed, Parallel, and Cluster Computing
- Systems and Control
- Hardware Architecture
- Computational Complexity
- Cryptography and Security
- Discrete Mathematics
- Computer Science and Game Theory
- Performance
- Human-Computer Interaction
- Digital Libraries
- Mathematical Software
- Data Structures and Algorithms
- Computational Geometry
- Computation and Language
- Graphics
- Robotics
- Logic in Computer Science
- Multimedia
- Networking and Internet Architecture
- Computers and Society

- We present algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny particles, which has been proposed in the context of programmable matter and self-assembly for building high-yield micro-factories. The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle; particles can bond when being forced together with another appropriate particle. Due to the physical and geometric constraints, not all shapes can be built in this manner; this gives rise to the Tilt Assembly Problem (TAP) of deciding constructibility. For simply-connected polyominoes $P$ in 2D consisting of $N$ unit-squares ("tiles"), we prove that TAP can be decided in $O(N\log N)$ time. For the optimization variant MaxTAP (in which the objective is to construct a subshape of maximum possible size), we show polyAPX-hardness: unless P=NP, MaxTAP cannot be approximated within a factor of $\Omega(N^{\frac{1}{3}})$; for tree-shaped structures, we give an $O(N^{\frac{1}{2}})$-approximation algorithm. For the efficiency of the assembly process itself, we show that any constructible shape allows pipelined assembly, which produces copies of $P$ in $O(1)$ amortized time, i.e., $N$ copies of $P$ in $O(N)$ time steps. These considerations can be extended to three-dimensional objects: For the class of polycubes $P$ we prove that it is NP-hard to decide whether it is possible to construct a path between two points of $P$; it is also NP-hard to decide constructibility of a polycube $P$. Moreover, it is expAPX-hard to maximize a path from a given start point.
- We define the crossing graph of a given embedded graph (such as a road network) to be a graph with a vertex for each edge of the embedding, with two crossing graph vertices adjacent when the corresponding two edges of the embedding cross each other. In this paper, we study the sparsity properties of crossing graphs of real-world road networks. We show that, in large road networks (the Urban Road Network Dataset), the crossing graphs have connected components that are primarily trees, and that the remaining non-tree components are typically sparse (technically, that they have bounded degeneracy). We prove theoretically that when an embedded graph has a sparse crossing graph, it has other desirable properties that lead to fast algorithms for shortest paths and other algorithms important in geographic information systems. Notably, these graphs have polynomial expansion, meaning that they and all their subgraphs have small separators.