Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,795
questions
-2
votes
1
answer
171
views
Is it possible to sort by only knowing the sign of pairwise sums?
I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this ...
2
votes
1
answer
174
views
How many samples are needed to reconstruct a path?
Consider an input set of vertices $V$ and vertices $s,t\in V$.
The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be ...
- 9,408
1
vote
0
answers
71
views
Mapping of entire balls using Locality Sensitive Hashing (LSH)
LSH functions are useful for approximate nearest neighbor search.
They are usually defined, for distance metric $d$ and $c>1$ as follows:
A family of hash functions is $(r, cr, p_1, p_2)$-LSH ...
- 9,408
5
votes
0
answers
216
views
Is there a fast algorithm for inverting a sparse matrix?
I am doing research on a random-walk like problem. As a critical part of my solution, I need to invert a non-singular sparse matrix of size $n \times n$ and with $O(n)$ non-empty entries. I'm working ...
- 235
7
votes
2
answers
211
views
Determining how n-tuples are sorted as you search them?
I have a sorted list of $N$ n-tuples, but I do not know exactly how they were sorted. The person who sorted them did so by lexicographically ordering some permutation least-to-greatest. For example, ...
- 327
-1
votes
1
answer
83
views
How is additive error handled in this simple algorithm? 'Product of all elements'
Say we have two unit vectors $\hat{u}, \hat{v} \in \mathbb{R}^n$ where $\hat{u} = (u_1,...,u_n)$ and $\hat{v}$ approximates $\hat{u}$. $~\hat{v} = (u_1+\epsilon, ...,u_n+\epsilon)$ where $\epsilon = \...
2
votes
1
answer
98
views
In external memory, is grouping equal elements easier than sorting?
Sorting an array will put equal elements adjacent to each other. So, in no model of computation can grouping equal elements be harder than sorting. In the RAM model, grouping equal elements is $O(n)$ ...
- 327
2
votes
1
answer
95
views
Longest stack-sortable subsequence
Given an array of $n$ pairwise-different positive integers, the problem is to find the longest subsequence that is stack-sortable, i.e. avoiding the permutation pattern $231$.
How fast can this ...
- 193
2
votes
0
answers
187
views
Shortest s-t path when is allowed to ignore k weights
Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed ...
- 112
2
votes
0
answers
70
views
Complexity of comparing extended integer power towers
Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by ...
- 633
2
votes
0
answers
94
views
Finding 3SUM witness when promised a solution
Suppose we have a 3SUM instance given with the promise that there exists at least one solution. Is the trivial $O(n^2)$ (modulo logarithmic improvements) solution still the best algorithm or is there ...
- 1,177
1
vote
0
answers
112
views
Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands
Has anyone studied the asymptotics of problems in complexity classes like $BPP$? The thought came to me that if a problem in $BPP$ only requires $O(log(n))$ bits of entropy to solve then, intuitively, ...
- 1,131
7
votes
1
answer
177
views
Arranging letters to make a word in a regular language
Fix a regular language $L$ on the alphabet $\{a, b\}$, and consider the following problem. I am given as input:
some number $m \in \mathbb{N}$ of copies of the letter $a$, and
some number $n \in \...
- 8,234
12
votes
1
answer
883
views
What is the hardest instance for the group isomorphism problem?
Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, ...
- 177
3
votes
1
answer
233
views
How is SDP an extension of spectral algorithms?
In one of his lectures, Uri Feige described semidefinite programming (SDP) as
... an algorithmic technique that extends both linear programming and spectral algorithms.
I know the basic ...
- 610
1
vote
1
answer
94
views
The SQ argument in Balazs Szorenyi's paper
I am asking about the proof in Theorem 5 (page 6) of this paper,
http://www.inf.u-szeged.hu/~szorenyi/Cikkek/sq_d0_ext.pdf
Quite a few things about this short argument seem unclear to me,
Towards the ...
- 1,443
11
votes
0
answers
253
views
Computational Complexity of the Frobenius Problem
The Frobenius problem takes as input $n$ positive integers $a_1,\ldots,a_n$ with $\gcd(a_1,\ldots,a_n)=1$ and asks for the largest integer $F$ that cannot be written in the form $F=a_1x_1+a_2x_2+\...
- 219
1
vote
2
answers
139
views
Enumerate all allocations of points in a simplex
Consider the standard 2-simplex $\{(x,y)~|~x+y=1~;~ x,y\geq 0\}$.
Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y by the following process:
Fix two positive ...
- 1,924
1
vote
0
answers
121
views
Minimising the maximum distance to the centre of a cluster of points
I have a set of points $C_i$ on a two dimensional plane and I want to find a point $P$ such that the maximum distance from $P$ to any of the points is minimised, i.e. minimise(max($||P-C_i||$)).
I've ...
- 21
4
votes
1
answer
156
views
Generalizations of linear programming
Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs.
Is there a survey/lecture notes describing ...
- 610
3
votes
0
answers
42
views
Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q
As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in ...
- 131
6
votes
1
answer
265
views
Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)
In the wikipedia article on Time Complexity it is written that:
The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, ...
- 1,987
2
votes
2
answers
560
views
About learning a single Gaussian in total-variation distance
I am looking for the proof of this following result which I saw as being claimed as a "folklore" in a paper. It would be helpful if someone can share a reference where this has been shown!
Let $G$ ...
- 1,443
6
votes
0
answers
195
views
Bottleneck $k$-link path in a complete DAG
Let $G$ be a complete DAG: It has vertices $v_1,\ldots,v_n$, and $v_iv_j$ is an edge if and only if $i<j$.
Let $w(i,j)$ be the weight of the edge $v_iv_j$. The weight has the property that $w(i,j)&...
- 4,367
1
vote
0
answers
14
views
Size of solutions in integer programming
Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
- 12.6k
4
votes
0
answers
191
views
What's the fastest known algorithm for finding the diameter of a graph?
Given a positively weighted graph what's the fastest algorithm for finding the diameter for that graph?
- 195
2
votes
0
answers
137
views
What is the competitive ratio of a $d$-way associative LRU cache?
In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$.
It is well known that for ...
- 9,408
0
votes
1
answer
131
views
Permuting the columns of a 0/1-matrix to avoid short segments
Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment ...
6
votes
0
answers
137
views
Evaluating addition chains
I hope this is a suitable place to ask this question.
An addition chain of size $n$ is a sequence $x_1, \dots, x_n$, where $x_1$ is fixed to 1 and $x_i = x_j + x_k$ for some $j,k < i$. I am ...
- 161
1
vote
0
answers
64
views
PTAS for projective clustering : survey
$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $k$ $j$-flats in $\mathbb{R}^d$ that minimizes the cost function as defined below:
Given a $j$-...
- 265
-4
votes
2
answers
96
views
Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]
Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted.
(notice how many times the 2 is touched [circled in red ...
- 87
5
votes
1
answer
79
views
Pop desired elements on stacks of bounded capacity
Consider there are $k$ stacks containing a total of $n$ elements. Each element is either red or blue. We have complete knowledge of each element's location and color.
Only push and pop are allowed on ...
- 4,367
-1
votes
1
answer
69
views
Formally prove that the loops of this sorting algorithm will terminate [closed]
Given is the sorting algorithm Bubblesort
...
- 117
5
votes
1
answer
235
views
Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates
Let $(X,+,\cdot)$ be a commutative ring. Let $|\cdot|\colon X\to \mathbb{N}$ be a function that satisfies $|x+y|\leq |x|+|y|$ and $|xy|\leq |x|+|y|$. We call the function length, and length is always ...
- 4,367
2
votes
1
answer
130
views
Find shortest prefix to generate original string by overlapping
Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed).
For ...
- 21
3
votes
0
answers
193
views
How to write algorithms?
Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to"...
user45424
2
votes
1
answer
120
views
Minimization version of matrix p-norms?
I considered a minimization version of matrix p-norms, defined for a matrix $A$ by
$$
f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.
$$
Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
- 31
3
votes
1
answer
89
views
What is the maximal load of a "latency-bounded" Cuckoo Hash?
Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time.
They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is ...
- 9,408
18
votes
1
answer
2k
views
Algorithm whose running time depends on P vs. NP
Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
- 317
6
votes
2
answers
324
views
Algorithm for identifying unprovable statements
I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms?
For example: If there ...
- 1,566
9
votes
3
answers
839
views
Non-Orthogonal Vectors Problem
Consider the following problems:
Orthogonal Vectors Problem
Input: A set $S$ of $n$ Boolean vectors each of length $d$.
Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
- 5,045
2
votes
0
answers
100
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.
...
- 311
7
votes
1
answer
173
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,177
14
votes
1
answer
551
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,422
3
votes
0
answers
94
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,422
8
votes
0
answers
136
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
232
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
278
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
753
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