Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,791
questions
0
votes
0
answers
23
views
What Data Structure storing points in space for fast lookup of stored points "near" a query point?
In NLP a common problem is that you have vector embeddings of large vocabularies, and you do manipulations on these vector embeddings to compute some result vector, and then you want to find which ...
- 101
5
votes
2
answers
501
views
Find odd-ranked numbers from a list
From a list of $n$ distinct numbers, I want to find the set consisting of all odd-ranked numbers (1st, 3rd, 5th, ...). How many comparison queries do I need?
I could sort the whole list using $O(n\log ...
- 113
3
votes
0
answers
70
views
Why do some problems seem to admit a richer family of algorithms than others?
Let's take integer multiplication and comparison sorting as examples. Despite being roughly comparable in terms of computational complexity, if we look at the set of algorithms which solve each ...
- 503
1
vote
0
answers
47
views
Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them
In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with ...
0
votes
0
answers
26
views
Complexity of XOR-Knapsack
Edit: Actually I should have been more careful. Maybe the optimal way to solve this is to approach it as a series of $k'-$XOR sum problems (Generalized birthday due to Wagner) for increasing $k'.$ And ...
- 2,039
1
vote
0
answers
46
views
Is there a calculus or formalism for measuring set relations between algorithm outputs?
I'm asking this question from a fairly naive position, so apologies in advance, etc.
I'm aware of the Bird-Meertens formalism for equational reasoning about algorithms but what I'm really interested ...
- 111
0
votes
1
answer
177
views
Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties
Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define
$$
f_{\mathfrak S}(z) := \sum_{\...
- 291
3
votes
2
answers
144
views
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
Let $n$ be a large positive integer. Give a nonempty collection $\mathcal S$ of subsets of $[n] := \{1,2,\ldots,n\}$, define an inner-product on $\mathbb R^n$ by
\begin{eqnarray}
\langle x,y\rangle_{\...
- 291
2
votes
0
answers
60
views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined.
One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 597
1
vote
1
answer
45
views
$k-$median problem and filtering technique Lin and Vitter
I read a paper from Tardos et al. about $k-$medians in metric space problem:
Given $N$ as set of points in metric space with distance function $c_{ij}$ for each $i,j\in N$, demand $d_i$ for each point ...
- 113
0
votes
0
answers
61
views
Why does the prefix sum operation require its binary operator to be associative?
Prefix Sums and Their Applications states that
The all-prefix-sums operation takes a binary associative operator ⊕, and
an ordered set of n elements...
Why is associativity a required property of ...
0
votes
1
answer
74
views
An inequality about median of points in higher dimensions
Let $S$ be a set of points in $\mathbf{R^d}$ and let $m$ be the median of this set of points, i.e. $\sum_{x \in S} || x - y||$ is minimized when we have $y=m$. Now let $z$ be an arbitrary point in $\...
- 1
1
vote
0
answers
61
views
On parallel complexity of modular inverse
Modular inverse is not known to be in $NC$ either.
How about the cases where the modulus is just $2^k +i$ where $i\in\{-1,0,1\}$?
Are these cases in $NC$?
- 12.6k
0
votes
0
answers
63
views
Maintaining a $K_{3,3}$-minor-free graph
Suppose we are given that an undirected, connected graph $G$ is $K_{3,3}$-minor-free.
Let $a,b\in V(G)$ be non-adjacent vertices.
Under what conditions is the graph that results by adding the edge $(a,...
- 95
0
votes
1
answer
51
views
Spectral sparsification of graphs with negative edge weights
I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question.
It is ...
- 1
11
votes
1
answer
1k
views
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
- 8,223
1
vote
0
answers
98
views
On the borderline between natural and artificial problems
While there is no formal definition of what constitutes a natural algorithmic problem,
in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
- 10.8k
1
vote
1
answer
68
views
Prefix free code unbalancing 0 and 1 bits
We have a long message $m$ to encode. The message is composed of a set of symbols $\{s_i\}$. Let $p_i$ denote the number of appearance of $s_i$ in $m$. We seek to find a prefix-free code for each $s_i$...
- 113
2
votes
0
answers
38
views
Algorithms for parametric matroid optimization
Let $M$ be a rank $r$ matroid with basis set $\mathcal{B}$ and an independence oracle. Given a linear function $w_e$ on each element $e$ of the matroid, we want to find the minimum weight basis for ...
- 4,327
0
votes
1
answer
210
views
Where should I start?
I am a college student majoring in Computer Science, before my college, I played OI for about 2 years. I want to learn tcs cuz I like it. Among the many tcs fields, I am most interested in algorithms. ...
- 101
0
votes
0
answers
55
views
Uniformly redistributing items across bins. What problem is this?
I'm trying to find reading material on a particular problem I'm interested in, but I don't know the terms to search.
Problem assumptions/definitions:
We have finite number of items I with weights [0, ...
- 101
2
votes
0
answers
51
views
Has there been any research on faster tensor inner products?
Matrix multiplication is a well studied problem which is recently back in the news due to deepmind.
That got me wondering has anyone looked at the more general problem of faster tensor multiplication? ...
- 369
0
votes
0
answers
31
views
Computing a feasible exchange bijection between bases of a matroid
A base-orderable matroid is a matroid in which, for any two bases $A$ and $B$, there exists a feasible exchange bijection, that is, a bijection $f: A\to B$ such that, for all $a\in A$, both $A-a+f(a)$ ...
- 1,880
4
votes
1
answer
160
views
Graph coloring with limit on number of times a color is used
Are there any results on coloring a graph using a limited number of each color. In other words, the decision problem would be: given a list of colors $C = (c_1, \dots, c_k)$ where each color $c_i$ is ...
- 43
0
votes
0
answers
59
views
Examples of Gaussian randomized algorithms
I've been thinking about algorithms of the form where a quantity $c$ can be viewed as the expectation of some estimator (random variable) $X$ and the expectation is taken over some multivariate ...
- 101
-1
votes
1
answer
49
views
Flow of value lower bounded by $X$
In a given network, is it possible to find a flow of value that is lower bounded by $X$ in near-linear time, $O((m + n) \text{poly}\log n)$? I do not want to find the exact maximum flow just whether ...
1
vote
2
answers
72
views
Examples of promise search problems that are easier than their non-promise variants?
By promise search problem, I mean a search problem for which the solution is guaranteed to exist (e.g. find a solution to a linear system of equations, knowing that a solution does exist).
Are there ...
- 209
1
vote
0
answers
83
views
Is there a better-than-brute-force algorithm for finding a largest subrelation that is a non-strict partial order?
Suppose we are given a finite binary relation $R$ and we are asked to find a largest subrelation of $P \subseteq R$ satisfying the properties of a (non-strict) partial order.
A brute force approach ...
- 111
-1
votes
1
answer
104
views
Need more explaination on this 'generality'
I am trying to understand how this proof works
I don't understand, why this f' is nondecreasing? What kind of generality makes us come up with such kind of assumption?
Please, I am weak.
- 101
0
votes
0
answers
109
views
In the Schönhage-Strassen algorithm for integer multiplication, when we calculate the product of two n-bit integers, why do we do so modulo 2^n + 1?
I ask this because it seems to me that there might be a loss of information here. The product of two n-bit integers could be up to 2n bits long, but any element of the integers modulo 2^n + 1 is at ...
1
vote
0
answers
49
views
Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?
Most problems about cutting graphs into roughly equal parts such as Sparsest cut, Graph partition, Balanced Cut, etc are based on minimizing the size of an edge cut. Even if all of those problems are ...
- 11
2
votes
0
answers
117
views
Open problem on *Finite Memory Clocks* by Tom Cover
This problem was proposed by Tom Cover in Open Problems in Communication and Computation (Cover and Gopinath, eds), 1987:
How does one tell time when the number of states in the clock is
insufficient ...
- 2,039
2
votes
0
answers
80
views
Finding Hamilton cycles in random graphs
For a random graph $G$ of minimum degree 3, can we find a Hamilton cycle in linear time (with high probability for every edge density)?
If this is an open problem, I will also accept an empirically ...
- 2,402
3
votes
1
answer
144
views
Do Knuth-Morris-Pratt and Booth’s LCS algorithm work in linear time on lists of lists of integers?
As a subroutine for an algorithm we’re working on, we need to compute the lexicographically minimal rotation (or least circular shift) of a list of lists of integers.
The problem, in the more usual ...
3
votes
0
answers
87
views
Linear time in-place stable sort
Surprisingly, linear time in-place stable sort is possible with integer keys of $O(\log n)$ bit length.
An algorithm appeared in Radix Sorting With No Extra Space (Franceschini, Muthukrishnan, ...
- 2,402
1
vote
0
answers
27
views
Existing results and hardness for dynamic dominance reporting
I am looking for state-of-the-art results on dynamic dominance reporting. In the dynamic dominance reporting problem, we have a set of k dimensional points and the goal is to maintain a data structure ...
- 1,167
1
vote
1
answer
167
views
Decomposition of a permutation into increasing subsequences
Given a permutation $P$, the goal is to decompose this permutation into $k$ increasing subsequences $L_1,L_2,\ldots,L_k$, such that every element in $P$ appears exactly once in some increasing ...
- 137
1
vote
0
answers
114
views
How to measure the weirdness of algorithms?
Let $M$ is a polynomial $k$-tape Turing machine and $C^t(x)$ is a time-bounded Kolmogorov complexity.
Let $str_M(x)$ be a string of the following form:
$$str_M(x)=w_1^1\# w_2^1 \# ... \# w_{m}^1 ■ w_1^...
- 49
1
vote
0
answers
54
views
Find the minimum cost spider joining a root to some leaves
A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider.
I am interested in the following problem: We are given an undirected graph $G = (V,E)$...
- 597
1
vote
1
answer
109
views
Do reasonably competitive 3SAT algorithms ever have shrinking run-time distributions when measured as a probability density function?
The algorithms I know for solving 3SAT typically have exponential run-time distributions which become wider in their PDF as the number of variables, $N$, increases. For the exponential distribution ...
1
vote
1
answer
68
views
Would the following be an acceptable part of an algorithm if used for prime factorization
Suppose I have some super fancy algorithm for prime factorization. I want to demonstrate its potential on a difficult case, like an RSA sized number composed of two primes,$\space n=p_1p_2$. As far as ...
- 33
1
vote
0
answers
48
views
What is known about simultaneous protocol set disjointness?
Assume that Alice and Bob have sets $A,B\subseteq[n]$ of size $|A|=|B|=k$.
In the simultaneous protocol, they both send a message to Carol (that doesn't observe $A$ and $B$) which needs to determine ...
- 11
12
votes
2
answers
663
views
Quadratic lower bound
Consider three arrays $A,B,C$ of size $N$ consisting of integers. I want to verify the following constraint: for any two indices $0 \leq i,j < N$, $A[i] < A[j] \land B[i] < B[j] \implies C[i] ...
- 1,167
1
vote
0
answers
98
views
Efficient enumeration of connected functional digraphs (up to isomorphism)
Together with the research intern I am supervising, we are currently writing some software that requires us to enumerate all connected functional digraphs of $n$ vertices up to isomorphism (also known ...
5
votes
1
answer
320
views
Deciding if all matrix multiplication entries have at least two witnesses
Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N×N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C=AB$ (not boolean matrix multiplication but the ...
- 1,167
1
vote
0
answers
85
views
Survey of Quantum Algorithms similar to Montanaro's from 2015
The survey https://arxiv.org/abs/1511.04206 by Montanaro is very nice in terms of giving a bird's eye view, which is very useful. As the author states in the abstract
Here we briefly survey some ...
- 2,039
1
vote
0
answers
24
views
Can fair ordering of transactions be achieved in permissionless blockchains?
Front running attacks mainly happen because adversaries are able to manipulate the order of the transactions on blockchains.
As many research paper address the problem of fair ordering, I don't find ( ...
- 11
0
votes
0
answers
71
views
Algorithms with advices of huge precomputed data
My main interest is complexity theory, and I'm studying the large or huge advice of Turing machines in the ongoing work.
As related to the study, I'm wondering what's known about "precomputation&...
- 689
1
vote
0
answers
25
views
Processing times of different job types on $n$ processors
I have $n$ processors that each receive an infinite sequence of jobs that have different processing times.
In the simplest case, $n = 2$ and jobs are either $\texttt{fast}$ or $\texttt{slow}$ with ...
- 131
6
votes
2
answers
270
views
How to show that the median cannot be maintained in $O(1)$ time?
Suppose that we have a stream of numbers $x_1,x_2,\ldots$ such that we wish to track the median of the values observed so far.
This task is easy to do with $O(\log n)$ update time (where $n$ is the ...
- 63