Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

learn more… | top users | synonyms (1)

3
votes
1answer
120 views

Applications of Harrow's algorithm for solving linear equations

In Harrow's algorithm for solving a system of linear equations the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a ...
-1
votes
0answers
36 views

What techniques are there for asking about satisfiability of a first order of a sentence? [on hold]

In reading about SAT in general and applications in first order logic, I've noticed that there are algorithms for answering the question of if a particular instance of a propositional sentence is ...
1
vote
0answers
73 views

Complexity of an algorithm for deciding 3-colorability of graph by the chromatic polynomial modulo $x-3$

As explained on MO computing the chromatic polynomial $P(G,x)$ modulo $x-3$ is enough for deciding 3-colorability. For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added ...
0
votes
0answers
33 views

An efficient method to find the MLE of the combination of two point processes

[Cross-posted from http://mathoverflow.net/questions/176402/an-efficient-method-to-find-the-mle-of-the-combination-of-two-point-processes ] I have a point process defined in two parts as follows. ...
5
votes
0answers
65 views

Perfect hashing family variation - injectivity on $r$ disjoint sets

We denote by $[t]$ the set $\{1,2,\ldots,t\}$. A $(n,k)$-perfect hashing family is a set of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S ...
0
votes
0answers
28 views

Sparse matrix-vector multiplication materials needed

I've been assigned a project at school, the theme is the influence on cache memory when doing sparse matrix-vector multiplications. I've been searching for materials for quite some time but all I can ...
0
votes
1answer
166 views

Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms

What are notable examples of problems for which the best currently known algorithm has $2^{\Theta(n^2)}\text{poly}(n)$ running time ?
6
votes
0answers
38 views

Explicit error bounds on the abelian hidden subgroup problem

What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries? Ettinger, Hoyer, and Knill give a result that the ...
-2
votes
0answers
68 views

Laplace's Demon [closed]

Can we apply Laplace's Demon anywhere in theoretical computer science? Laplace's Demon talks of an "all-knowing intellect" at a universal level, isn't it possible to apply the same to any ...
-1
votes
0answers
40 views

Developing Matrix Chain Multiplication Algorithm [closed]

Supposing, we don't know the DP algorithm for MCM. What could be the line of thought, that will lead us to the solution?(or develop it) Starting with the brute force method, we can examine all ...
0
votes
0answers
61 views

The ratio $\frac{f(x_{i})-f(x_{i+1})}{||x_{i+1}-x_i||_2}$ as a performance index

Consider a problem \begin{equation} P:\min_{x \in X} f(x) \end{equation} Suppose it can be solved by an iterative method $A:X \rightarrow X$ $x_{i+1} = A(x_i)$ and $f(x_{0})\geq f(x_1) \geq ...
-1
votes
0answers
58 views

Making a function tail-recursive without using CPS

Is there a way to compute $\binom{n}{k}$ through the recurrence $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ in a tail-recursive manner using only the basic structures found in mainstream ...
-2
votes
0answers
39 views

Data structures in Clauset-Newman-Moore algorithm for finding community structure in networks?

I am trying to implement the Clauset-Newman-Moore algorithm for discovering community structure in python. The paper describing the algorithm is in the comments because I cannot post more than 2 links ...
2
votes
1answer
53 views

Efficient (non-crypto-grade?) pseudorandom permutations with arbitrary domain size

I'm looking for an efficient/simple (even if not necessarily cryptographically strong) algorithm for implementing pseudorandom permutations with domain cardinality other than a power of 2. (FWIW, the ...
3
votes
1answer
169 views

Does a universal index exist?

Given a data table containing a very large number $N$ of rows, with each row containing a large number $k$ of fields, with each field containing a large but fixed number of bits, there are a number of ...
10
votes
1answer
77 views

Minimum equidecomposable decomposition

Given two polyhedra $P$ and $Q$, $P$ and $Q$ are are equidecomposable if there are finite sets of polyhedra $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ such that $P_i$ and $Q_i$ are congruent for all ...
-1
votes
0answers
27 views

eigenvalue of the product of a circulant matrix and diagonal matrix

Suppose we have a circulant matrix (A) and a diagonal matrix (B). Both of the matrices are of order n * n. The elements in the diagonal matrix are all different. Is there an algorithm to compute the ...
0
votes
0answers
74 views

Regularlity lemma and exceptional set

Regularity lemma is one of the most basic tools in algorithmic thoery and pure math theory like additive number theory and combinatorics. This lemma is stated two ways: the existence of a partion ...
6
votes
2answers
196 views

What is the value of this “game” (counters rebalancing)?

This question was posted in CS.SE two weeks ago, but it didn't get a satisfying answer. Suppose you have the following game: There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized ...
4
votes
0answers
74 views

How many exponentiations can the Shamir algorithm reduce?

The Shamir's algorithm is depicted as follows (cited from Handbook of Applied Cryptography, chapter 14, algorithm 14.88, page 618) Shamir's algorithm INPUT: group elements $g_0,g_1,\dots, g_{k-1}$ ...
7
votes
2answers
213 views

Maximizing the number of heads in $N$ tosses by choosing which coin to toss

Assume you have two coins $A,B$ with biases $P_A,P_B$ respectively. We would like to make $N$ coin tosses and get the maximal number of heads possible. Unfortunately, we know $P_B$, but $P_A$ is ...
-1
votes
0answers
28 views

Trees, and how to organize data and answer queries efficiently

Suppose there exists a set $X$, containing zero or more elements of some type, and we'd like to run a query, as efficiently as possible. For many interesting queries - value associated with a key, ...
4
votes
2answers
444 views

Sum of products of all combinations?

We are given a list $S$ containing $n$ numbers $S=(s_1,\ldots, s_n)$. Let $S \choose k$ be the set of all possible $k$-combinations from $S$ (i.e. size $k$ subsets of $S$). We want to compute the ...
10
votes
1answer
226 views

Identifying useless edges for shortest path

Consider a graph $G$ (the problem makes sense both for directed and undirected graphs). Call $M_G$ the matrix of distances of $G$: $M_G[i, j]$ is the shortest path distance from vertex $i$ to vertex ...
7
votes
1answer
152 views

Is the feasible region of this SDP polyhedral?

We have a semidefinite program (SDP) with feasible region containing only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral? We believe this to ...
4
votes
2answers
195 views

Intuitively, why is the complementary slackness condition true?

What's an intuitive proof that shows that the conditions of complementary slackness are indeed true: If $x^*_j > 0$ then the $j$-th constraint in the dual is binding. If the $j$-th constraint in ...
3
votes
1answer
121 views

Number of bits required for encoding variables with fixed sum?

Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$ It's easy to store the variables using ...
6
votes
1answer
175 views

Why is complementary slackness important?

Complementary slackness (CS) is commonly taught when talking about duality. It establishes a nice relation between the primal and the dual constraint/variables from a mathematical viewpoint. The two ...
3
votes
2answers
85 views

Minimal encoding of a set (unordered collection of elements)?

Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$. If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are ...
0
votes
2answers
123 views

Determining the distribution of results of a simple algorithm

Setting Consider repeating the following process on the numbers $N=\{1, 2, 3, \ldots, n\}$: Pick an integer $k \in N$, uniformly at random. Pick a subset of $k$ elements from $N$, uniformly at ...
1
vote
1answer
52 views

Are there published algorithms for on-line creation of AVL trees from ordered streams?

Given an ordered stream of n items (n unknown in advance), it is well-known how to construct a red-black tree from them in O(n)-time. More specifically this is possible using only O(log n) additional ...
4
votes
0answers
64 views

What is known about finding heavy hitters in a sliding window?

This question is strongly related to another question I asked here a few weeks ago. In this problem setting we have a stream of elements $s_1,s_2,...$, such that $\forall i: s_i\in \mathcal X$ for ...
11
votes
3answers
418 views

How to iterate over vectors in order of probability in small space

Consider an $n$ dimensional vector $v$ where $v_i \in \{0,1\}$. For each $i$ we know $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent. Using these probabilities, is there an efficient ...
4
votes
0answers
57 views

What is the smallest deterministic construction of an ordered perfect hashing family?

A $(n,k)$-perfect hashing family is a family of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $H_S$ is injective on $S$. ...
9
votes
1answer
132 views

Checking if a polynomial factors into linear factors

Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given by an arithmetic circuit $C$ of size $s$. Given $C$ as the input, is there a deterministic algorithm to check whether all the ...
0
votes
1answer
30 views

Why is label pruning possible with hub labeling?

Hub labeling (HL) computes superlabels using the vertices visited by the forward and reverse Contraction Hierarchies (CH) search. Those labels are then pruned (see HL, sec. 4.2) to generate strict ...
4
votes
1answer
181 views

Intersection of two unsorted sets or lists

Suppose you are given two lists $L_1$ and $L_2$, each of which contains pairwise distinct elements from some set $S$. What is the complexity of computing the intersection $L_1\cap L_2$ of the two ...
1
vote
2answers
73 views

Difference between PRAM and machine model in dynamic multithreading

In the first edition of Introduction to Algorithms (Cormen et al., MIT Press, 1990), the discussion of parallel algorithms is based on the PRAM model. In the second edition, paralellism has been ...
5
votes
0answers
108 views

Best algorithm for inversion of symmetric positive-definite matrices

As I know, the time complexity for usual inversion algorithm of general matrix is $O(n^3)$. In recent years, there is a improvement from $O(n^3)$ to $O(n^{2.8....})$. However, does there exists a ...
4
votes
3answers
361 views

Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?

An "algorithm" for calculating $ax+b$ would take the steps Calculate $a$ times $x$ Calculate $b$ plus the result of previous line. But if the values of $a$ and $b$ are known, can we create a more ...
0
votes
0answers
59 views

Are there any approaches to the following scheduling problem?

Consider the following problem: we are given $K$ tasks $\langle n_1, n_2, ..., n_K \rangle$. Every task $n_i$ is qualified with two parameters: The time it takes to be completed ($t_i$) and, The ...
2
votes
1answer
153 views

Literature for Generalized Load Balancing

i am looking for literature on this kind of problem. $$ \begin{align} \min_x \max_k &\quad \sum_{i,j} x_{ij}c_{ijk}\\ \text{subject to}&\\ &\sum_j x_{ij}=1,&& \forall i\in\mathcal ...
8
votes
0answers
187 views

Additive error in counting the number of 1's in a sliding window?

The setting is as follows: We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's ...
5
votes
0answers
157 views

Practical algorithm for testing whether an edge is Delaunay

I have a set of vertices $V\subset\mathbb R^3$ and a set of edges $S=\{(a,b)|a,b \in V\}$. I want to know whether an edge in the set $S$ is Delaunay against the vertices in $V$. My assumed ...
1
vote
1answer
81 views

Why does the construction step of Aho-Corasick take linear time in the number of nodes?

The original paper's analysis of this, as far as I can tell is this: "THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords. PROOF. Straightforward." ...
3
votes
0answers
138 views

Election algorithm with unreliable messages and a certain timestamp

I am struggling to get a correct algorithm for a leader election algorithm in a distributed system. My assumptions are as follows: Messages are sent unreliably with an at-most-once sending Nodes are ...
1
vote
0answers
165 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
1
vote
1answer
87 views

Asymmetry in converting Burrows-Wheeler transform to suffix array?

Given a suffix array of a string $w$, it's possible to construct the Burrows-Wheeler transform of $w$ by subtracting one from the indices of the suffix array (wrapping around if necessary), then ...
9
votes
1answer
148 views

Bisecting a set of points into two optimal subsets

I want to divide a set of points into two equally-sized subsets such that the within-cluster sum of squares is minimized. We can assume that the points are in two-dimensional Euclidian space. I'm ...
0
votes
0answers
56 views

Greiner-Hormann clipping with degeneracies

I'm trying to understand the paper "Clipping of Arbitrary Polygons with Degeneracies" by E. L Foster and J. R. Overfelt [1], which claims to extend the classic Greiner-Hormann polygon clipping ...