Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,754
questions
2
votes
0
answers
98
views
On the goal of learned clause database reduction in CDCL SAT solvers
Modern SAT solvers frequently reduce the size of their learned clause database in order to keep its size as manageable as possible. This has as effect not to slow down the speed of unit propagations.
...
- 301
7
votes
1
answer
162
views
Lower bound for enumerating k closest pair of points
Consider 1 dimensional points $x_1, \dots x_n, x_i \in \mathbb{R}$ where the distance between any two points is defined as $d(x_i, x_j) = \vert x_i - x_j \vert$. The goal is to enumerate all $n^2$ ...
- 1,015
14
votes
1
answer
523
views
Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons
Is there a comparison-based sorting algorithm that uses an average of $\mathrm{lg}(n!)+o(n)$ comparisons?
Existence of a worst-case $\mathrm{lg}(n!)+o(n)$ comparison algorithm is an open problem (...
- 2,237
3
votes
0
answers
86
views
Lower bound for reversing a list using queues
How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues?
Each queue is FIFO. Time refers to the number of operations on the queues.
...
- 2,237
8
votes
0
answers
134
views
Finding $n$ many different primes efficiently
I want to find $n$ many different primes on RAM. I can find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ in $O(n)$ running time. A brute force way is to find $O(\frac{n}{\log n})$ many ...
- 420
14
votes
1
answer
1k
views
Deciding whether an interval contains a prime number
What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the ...
1
vote
0
answers
228
views
Impagliazzo lemma, unclear detail in its proof
In Arora-Barak's book on page 378 in the proof of Impagliazzo's Hard Core lemma why did they choose the number 50 in this line: Set $t = \frac{50n}{\epsilon^2}$ ? How this choice then yields the size ...
- 317
5
votes
1
answer
232
views
What does "hold uniformly" mean in the context of asymptotic analysis?
What does "hold uniformly" mean in the statement of Theorem 1.7 in
A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):
4
votes
1
answer
698
views
Fast algorithm to find a maximum connected subgraph of k vertices
Given an undirected graph $G = (V, E)$ and a function $f: 2^V \to \mathbb{R}^+,$ where $2^V$ is the set of all subsets of $V$. Find a connected subgraph $T = (V_T, E_T)$ of k vertices such that $f(V_T)...
- 141
1
vote
0
answers
58
views
Minimization of the maximal adjacent integer sums on a circle
Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? For specific and low $n$'s it has been pointed out in math.stackexchange....
- 113
3
votes
2
answers
306
views
What is the best approximation and exact algorithm for vertex cover on cubic graphs?
"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
- 41
7
votes
1
answer
195
views
How to solve this generalization of binary search?
Let $f:\{1,\ldots,n\}$ be a monotonically non-decreasing function.
Consider, for some unknown threshold $1\le T\le n$, a threshold function
$$g(x)= \begin{cases}
0&\text{x<T}\\
1&\text{...
- 9,378
3
votes
1
answer
53
views
Complexity of distributively verifying that the diameter is small
Consider a graph $G=(V,E)$ and an integer parameter $k$.
I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ...
- 9,378
4
votes
0
answers
114
views
2-hop distributed coloring in the CONGEST model
Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$.
A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \...
- 9,378
2
votes
0
answers
315
views
Career advice needed: Switching from theoretical CS to pure math
I couldn't think of a better forum to ask this question. I am a first year cs graduate student. I couldn't really pursue theoretical cs during my undergrad, but as part of our PhD qualifiers, i had to ...
- 137
2
votes
1
answer
236
views
Existence of an algorithm
I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting ...
- 21
7
votes
1
answer
132
views
Smoothed analysis to compare algorithms
Has there been any research using smoothed analysis to compare approximation algorithms that have the same approximation ratio?
Any research that compares algorithms using smoothed analysis would be ...
3
votes
1
answer
54
views
Algorithm for finding smallest set and instanciation for a given constraint system
I have a system of constraints described by a set of clauses of the form
$x_1 \neq x_2 \lor \dots \lor x_{i-1} \neq x_i$, for instance:
...
- 31
19
votes
4
answers
971
views
Problems that are counter-intuitively solvable in practice?
Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in ...
0
votes
1
answer
102
views
How can algorithms with nested combinatorial searches be quasi-linear?
I've come across algorithms similar to the one below, where a demanding step is performed, which should have at least polynomial complexity, yet the whole algorithm is deemed quasi-linear without ...
- 111
6
votes
1
answer
202
views
Anti bin packing
I have a (practically) unlimited amount of McDonald's coupons that I can use only if I shop for at least 1 money.
Thus I want to partition my family's meal into as many parts as possible that all ...
- 13.5k
-1
votes
1
answer
36
views
Algorithm in logarithmic time that finds a number with the help of a subarray that is not in the array
The question is as follows.
Given: A sorted array A of n integers where A[n − 1] − A[0] ≥ n.
Asked: Give an algorithm and the invariant of the algorithm that finds a number between A[0] and A[n - 1] ...
9
votes
5
answers
946
views
W[1]-hard problems with FPT time approximation algorithms
I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are:
R1. W[1]-hard.
R2. Admit a (preferably constant) approximation algorithm ...
- 9,378
4
votes
1
answer
369
views
"Smallest" path that visits a given set of vertices
I use smallest rather than shortest to distinguish between the shortest path problem. The problem is as follows:
Given a directed graph $G=(V,E)$, two vertices $s$ and $t$, and a set of $p$ ...
- 191
1
vote
1
answer
95
views
What is the best and easy (regarding implementation) way of computing three edge independent trees in a 3-connected graph?
I am searching for an implementation of an algorithm that constructs three edge independent spanning trees from a 3-edge connected graph. Any response will be appreciated. Thanks in Advance.
- 11
3
votes
1
answer
180
views
On complexity of linear programming with quadratic equality/inequality constraints?
Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ ...
- 12.5k
3
votes
0
answers
173
views
Fast way of getting a matrix of sums
We are given an array of variables $A$, along with a matrix $M$. The elements of the matrix $M$ are composed of sums of the variables in $A$. We are allowed to pre-process $A$ in order to find a ...
- 2,080
10
votes
2
answers
1k
views
Counterexample to max-flow algorithms with irrational weights?
It is known that Ford-Fulkerson or Edmonds-Karp with the fat pipe heuristic (two algorithms for max-flow) need not halt if some of the weights are irrational. In fact, they can even converge on the ...
- 35.7k
1
vote
1
answer
71
views
Does the following 2-rounds distributed algorithm approximates a maximal matching well?
Let $G$ be an undirected graph.
I'm looking for a two-rounds distributed algorithm that matches as many vertex pairs as possible.
Consider the following protocol for vertex $v$.
Use a fair coin to ...
- 9,378
1
vote
0
answers
176
views
How to represent boolean tree + algorithm as a mathematical formula
In programming say you have a boolean tree like this:
...
- 141
15
votes
1
answer
1k
views
Examples of algorithms and proofs that seem correct, but aren't
In my intro to programming course, we're learning about the Initialization-Maintenance-Termination method of proving an algorithm does what we expect it to. But we've only had to prove that an ...
- 153
2
votes
1
answer
142
views
Is there any time efficient way of achieving the result of FKS hashing lemma?
FKS hashing lemma states.
Given a set of $n-$bit numbers $\{x_1,x_2,\dots,x_k\}$ there exist a
prime $p$ of $O(\log n + \log k)$-bit such that $x_i$ mod $p \neq $
$x_j$ mod $p$ if $x_i \neq x_j$...
- 103
1
vote
1
answer
199
views
Minimizing SubModular Function: Cardinality
Given a submodular function f: 2^V to reals (not necessarily monotone), and an integer k, find a set S such that |S| <= k and such that f(S) is minimized.
When the size constraint is |S| >=k, the ...
- 19
1
vote
0
answers
61
views
What is the fastest gradient based algorithm to get to criticality of a "nice" non-convex function?
I am allowing for the following properties for a once differentiable non-convex $f : \mathbb{R}^d \rightarrow \mathbb{R}$,
(a) Let there be a $\sigma >0$ s.t the norm of the gradient of the ...
- 1,443
8
votes
1
answer
1k
views
Minimum cost topological ordering
We are given a $n$ vertex directed graph $G=(V,E)$ and also given a cost function $c:V\times [n]\to \mathbb{R}$. Consider a topological ordering of the vertices, $v_1,\ldots,v_n$, the cost of the ...
- 4,256
7
votes
1
answer
203
views
What is the fastest known algorithm for finding conjugacy classes?
Given a finite group $G$ of size $n$ by the table representation. I want to compute the conjugacy classes of group $G$. A trivial algorithm seems to take $O(n^2)$ operation ( $b = g^{-1}a g$ type ...
- 420
4
votes
0
answers
205
views
Find a pair of nodes with maximum sum of distances in k given trees
For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
- 235
3
votes
0
answers
118
views
Graph-related applications of the fast Fourier transform (and other algebraic algorithms)
The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. matchings and shortest paths).
However, while the fast Fourier transform algorithm implies several other near-...
- 1,120
2
votes
1
answer
401
views
Efficient algorithm for generating data dependency DAG from lists of memory ranges and access modes
Assume you are given:
A list of N (not necessarily distinct) memory ranges of the form [x,y], where x and y are non-negative integers representing the lower and upper bounds of the range, and
A list ...
2
votes
0
answers
65
views
Has Khachiyan/Porkolob's convex integer optimization been implemented?
Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
- 12.5k
8
votes
1
answer
421
views
Is abelian group isomorphism in $\mathsf{AC^0}$?
An $O(n^2)$ running time algorithm for abelian group isomorphism is easy to see. Later working on this problem in 2003 Vikas improve the result from $O(n^2)$ running time to $O(n \log n)$. In 2007, ...
- 358
1
vote
1
answer
219
views
How to compute GCD efficiently?
I want to compute $ A= \langle \text{GCD}(a,j),j=2,3,..,k-1\rangle$ and assume that each value of $j$ is less than $a$. I can compute GCD(a,j), $j=2,3,..,k-1$ and $a \le j$ for single fixed value of $...
- 358
2
votes
0
answers
65
views
What is the difference between PRAM and multi threading?
PRAM and multi-threading are somewhat part of the same model of the shared memory model, in which both can compute in parallel, and both can allow processors to communicate with each other since there ...
- 121
12
votes
1
answer
983
views
Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?
In the recent preprint https://arxiv.org/abs/1801.00776, it is claimed that $n$ real numbers can be sorted in time
$$O(n \sqrt{\log n}),
$$
and linear space. The paper seems reasonable, though I am ...
- 1,986
14
votes
2
answers
525
views
OR-circuit complexity of a dense linear operator
Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it ...
3
votes
0
answers
67
views
Is there some research about infinitely many-armed bandit with non-stationary assumption?
Is there some research about infinitely many-armed bandit with non-stationary assumption? I have found the paper about infinitely many-armed bandit under stationary (or stochastic) assumption. And I ...
- 31
2
votes
0
answers
66
views
Finding the largest set of points of limited diameter (2)
Problem: Given a set of points $S = \{(x_1, y_1), (x_2, y_2),\cdots,(x_n, y_n)\}$ in $\mathbb{R}^2$ and a distance threshold $\tau$, find a subset of $S$ such that (1) the Euclidean distance between ...
- 43
2
votes
0
answers
153
views
Is Normal centralizer problem in P? [closed]
Notations
$\le$ is used for subgroup
$G = \langle A \rangle $ means group $G$ is generated by set $A$
$P$ means polynomial time in input size.
$\Omega = \{1,2,3,\cdots,n\}$ is a input domain
Sym($\...
- 358
10
votes
6
answers
802
views
Can neural networks be used to devise algorithms?
After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I ...
- 13.5k
-3
votes
1
answer
156
views
Continous work distribution algorithm with failover
Imagine there's a system where there's N workers and M units of work, for example, N ≤ 64, M = 256.
Is there an algorithm that ...
- 95