Questions tagged [ds.algorithms]

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

Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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. ...
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? ...
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)$ ...
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 ...
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 ...
-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 ...
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 ...
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, ...
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)$...
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 ( ...
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&...
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

1
2 3 4 5
36