A special monomial is a monomial of the form $C\cdot x_{i_1} \cdot \ldots \cdot x_{i_n}$, where C is an integer and no variable is repeated more than once in the monomial. For inst …

LLL and other lattice reduction techniques (such as PSLQ) try to find a short basis vector relative to the 2-norm, i.e. for a given basis that has $ \varepsilon $ as its shortest v …

Throughout, by finite triangulation I mean a triangulation consisting of a finite number of triangles. Suppose $T$ and $T'$ are finite triangulations of a 3-manifold $M$. We will …

There are many fast algorithms (deterministic and probabilistic) for detecting primality. Are there any fast algorithms (probabilistic ones allowed) known for detecting whether a n …

Given an unweighted graph $G = (V, E)$, let the cut function on this graph be defined to be: $C:2^V \rightarrow \mathbb{Z}$ such that: $$C_G(S) = |{(u,v) \in E : u \in S \wedge v …

Given an unweighted graph $G = (V, E)$, let the cut function on this graph be defined to be: $C:2^V \rightarrow \mathbb{Z}$ such that: $$C(S) = |{(u,v) \in E : u \in S \wedge v \n …

I just got started with DCT/DST but I still fail to understand how the fast DST is supposed to work. The idea behind the FFT is rather apparent and there is very intuitive pseudo-c …

What is the most general class of metric spaces for which the closest pair of points in any finite subset can be found in time O(n^(1+eps))? I have studied how to do this in O(n l …

This question is related to the previous discussion here. Due to the result of Noga Alon et al., there is an $O((2k)^kn)$ algorithm for deciding whether a planar graph $G$ contain …

Most cellular automata are defined as being updated synchronously. I am interested in asynchronous automata, where they do not all have to update simultaneously. I am restricting …

I am interested in references about algorithms to be used in parallel distributed systems: how to generate, optimize, or evaluate the best way of processing information at multiple …

I have a probability problem, which I need to simulate in a reasonable amount of time. In it's simplified form, I have 30 unfair coins each with a different known probability. I th …

Besides the classical: you can't do comparison sort with faster than (n logn); what are other lower bounds we know of for algorithms? I can't seem to dig them up via google scholar …

I'm working on implementing a open source Public Transport Route Planner for Dublin. I have uploaded my source code and created a wiki on http://wiki.github.com/paddydub/Transport …

"Vinay Deolalikar. P is not equal to NP. 6th August, 2010 (66 pages 10pt, 102 pages 12pt). Manuscript sent on 6th August to several leading researchers in various areas. Confirmat …