Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
4 votes
1 answer
74 views

Reference request: finite field computation over the Word-RAM model

Let $q = p^\ell$ be a positive integer power of a prime $p$, of size $q = \text{poly}(n)$. Over the Word-RAM model (with words of size $O(\log n)$), how quickly can we perform addition and ...
Naysh's user avatar
  • 686
-1 votes
0 answers
56 views

Orthogonal Vectors algorithm in $O(n^{2-\varepsilon}d)$ when $d \le (2-\varepsilon)\log n$

For two sets of size $n$ of binary vectors in $\{0, 1\}^d$, can we do a $O(n^{2-\varepsilon}d)$ algorithm for Orthogonal Vectors problem on them if $d \le (2-\varepsilon)\log n$? I have checked https:/...
StarGazerD's user avatar
7 votes
0 answers
66 views

Tree of addition chains

Addition chains are a well-known way of building up a number from 1 by adding two previously computed numbers. It is a long-standing open problem to determine the complexity of computing the length of ...
domotorp's user avatar
  • 14k
1 vote
0 answers
66 views

Perceptual similarity problem in theoretical computer science

A perceptual hash is a type of locality-sensitive hash, which is analogous if the features of the images are similar. Let $I$ denote the set of images and $y_1 \approx y_2 $ means images are similar (...
David's user avatar
  • 123
3 votes
1 answer
113 views

How well can shortest common supersequence over small alphabet size be approximated?

Given a list $L$ of sequences of the first $n+1$ natural numbers, how well can we approximate the shortest common supersequence of all sequences in $L$? The paper here shows that if $n$ is not ...
Hao S's user avatar
  • 228
0 votes
1 answer
82 views

Polynomial time algorihtms for two variants of the decision version of longest walk problem

I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm. As I understand it, the longest path problem doesn't allow repetition of edges....
user1868607's user avatar
  • 1,019
0 votes
0 answers
52 views

Shortest sequence that contains a given list of sequences as subsequences

Given an alphabet with $n$ characters, and a list $L$ of sequences can we approximately find the shortest sequence that contains all sequences of $L$ as subsequences? Very similar to the question ...
Hao S's user avatar
  • 228
1 vote
1 answer
62 views

Shorter than target vector path algorithm

Consider a generalisation of the shortest path problem on directed graphs with weights in $\mathbb{Q}^k$. Formally, the input is a graph, a source state $s$, a target state $t$, and an objective ...
user1868607's user avatar
  • 1,019
2 votes
1 answer
387 views

A question on combinatorial algorithm

Given n sets $S_1,...,S_n$ such that $S_i \subset \{1,...,n\}$ is there a poly(n) algorithm to find $1 \leq i_1 < i_2 <.... < i_k \leq n$ such that $|\bigcup_{j=1}^k S_{i_j} | = k$ where $1 \...
Rishabh Kothary's user avatar
1 vote
0 answers
42 views

Constructing a DFA with $n$ states for which $L*$ needs $n$ equivalence queries

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
Coping Forever's user avatar
0 votes
0 answers
20 views

Detection of intersection between two $d$-dimensional convex polytopes with at most $N$ facets

I am looking for a reference on the current state-of-the-art algorithm(s) for detecting intersection between two $d$-dimensional convex polytopes, with time complexity depending on their number of ...
pyridoxal_trigeminus's user avatar
4 votes
0 answers
58 views

Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort for sorting array $a$ of size $n$. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how ...
orlp's user avatar
  • 885
0 votes
1 answer
53 views

Question about claw-free graphs

Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ? There are three induced paths through $u$: between $y$ and $z$ (i.e., $y \...
BBK's user avatar
  • 103
2 votes
0 answers
75 views

References for algorithms to compute approximating polytopes for arbitrary convex sets

There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes. One of the main results in this area is that under some mild ...
pyridoxal_trigeminus's user avatar
4 votes
0 answers
77 views

Uniform lower bounds in terms of the matrix multiplication exponent $\omega$?

Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is ...
Mingda Qiao's user avatar
0 votes
2 answers
213 views

Shortest path with permutations and fixed dimension

I'm thinking of extensions of the shortest path problem which are solvable in polynomial time. One way to do this is to consider the shortest path problem on a weighted directed graph with weights on $...
user1868607's user avatar
  • 1,019
0 votes
0 answers
95 views

What algorithms are there for ANN?

I'm a software engineer working on a large project for which one of the subcomponents involves approximately solving the nearest neighbors problem (to a factor of $1+\epsilon$). I was wondering what ...
Jaclyn's user avatar
  • 11
5 votes
1 answer
134 views

Shortest path with affine updates and fixed dimension

One may look at the shortest path problem on a weighted directed graph with weights on $\mathbb{Q}$ as the problem of minimizing a rational value $x$ which is updated at each edge of the graph with ...
user1868607's user avatar
  • 1,019
1 vote
1 answer
83 views

Is there a conditional lower bound for the k max subarray sum problem?

Consider an array $A$ of integers of length $n$. The $k$-max subarray sum asks us to find up to $k$ (contiguous) non-overlapping subarrays of $A$ with maximum sum. If $A$ is all negative then this ...
Simd's user avatar
  • 3,902
10 votes
2 answers
355 views

Algorithm to check whether a given set is Sidon

We call a set of natural numbers $\mathcal S$ to be a Sidon Set if $a+b=c+d$ for $a,b,c,d\in \mathcal S$ implies $\{a,b\}=\{c,d\}$. In other words, all pairwise sums are distinct. What algorithms do ...
Sayan Dutta's user avatar
3 votes
1 answer
134 views

Rearrange vectors so partial sums are all non-negative

Consider we are given a collection of $n$ vectors in $d$ dimensions, we want to decide if they can be rearranged into $v_1,\ldots,v_n$ such that $\sum_{i=1}^j v_i\geq \textbf{0}$ for all $j\in [n]$. ...
Chao Xu's user avatar
  • 4,479
3 votes
1 answer
75 views

What is the fastest algorithm for computing exact network reliability?

In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i....
Naysh's user avatar
  • 686
2 votes
1 answer
97 views

Maximum cardinality disjoint cycle cover in undirected graphs

I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
delete000's user avatar
  • 828
4 votes
1 answer
180 views

Is there a lower bound for the problem of finding the best straight line partition

I recently asked the following algorithms question on another site. The best answer so far is $O(n^4)$ time. The input is of size $O(n^2)$ and the output is just a number so I was wondering if there ...
Simd's user avatar
  • 3,902
0 votes
1 answer
136 views

Complexity of simplex method

What is the complexity of the simplex method in terms of Big O in the general case? I saw two variants: O(2^n) and O(2^(n+m)), where n is the number of variables and m is the number of constraints
Kitty's user avatar
  • 1
4 votes
0 answers
106 views

$\log^\star n$ is somewhat common in runtimes. Does the superroot ever make an appearance?

Many algorithms and data structures have iterated logarithms ($\log^\star n$) in their runtimes. This function is the discrete inverse of tetration, in that $$\log_a^\star (a \uparrow \uparrow b) = b$$...
templatetypedef's user avatar
10 votes
0 answers
157 views

Fine-grained complexity for game-type problems

My specific question is the following. Consider the following problem that I call Strange-TQBF: there is a Boolean function $f(x_1, \ldots, x_n)$ and two players Alice and Bob. They take turns ...
Alexey Milovanov's user avatar
57 votes
10 answers
18k views

Recent advances in computer science since 2010?

Since I left school (early 2010s) a couple of recently developed techniques were widely adopted by the industry. For example, Asymmetric numeral systems for compression (e.g. Ubuntu ships with ...
1 vote
0 answers
42 views

Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights

I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
Pablo Messina's user avatar
0 votes
0 answers
52 views

Deamortization of basic COLA (Cache oblivious lookahead array)

I am reading the paper titled Cache Oblivious Streaming B-trees. I am trying to understand the deamortization technique used for basic COLA. The paper says that for every level k, for deamortization, ...
debasishg's user avatar
8 votes
2 answers
499 views

Given real numbers $x_1,...,x_n$ , find the maximum of $ \frac{(x_j-x_i)^2}{j-i}$

Can it be done in linear or at least subquadratic time?
Scott Aaronson's user avatar
2 votes
0 answers
38 views

Generalization of Binary Decomposition to Polynomials?

Given an integer $x\in\mathbb{Z}$, we can write its binary decomposition (and more generally base $B$ for $B\in\mathbb{Z}$, $B>1$) as $$x = \sum_{i=0} x_i B^i,$$ where $x_i \in \mathbb{Z}/B\mathbb{...
Mark Schultz-Wu's user avatar
21 votes
10 answers
3k views

What are examples of recent relatively simple 'toolbox algorithms'?

Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc. There are also several relatively standard data structures, such ...
Per Alexandersson's user avatar
2 votes
0 answers
42 views

Effective algorithms for finite lattices of (higher-order) monotonous functions?

I am looking for references on effective algorithms on finite lattices or posets, and in particular on lattices of monotonous functions between two lattices, with higher-order structure -- monotonous ...
gasche's user avatar
  • 2,040
6 votes
1 answer
354 views

Condition Number dependent algorithms for matrix operations

Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
Thomas Ahle's user avatar
-1 votes
1 answer
93 views

How is memory being used by an algorithm, to define its space complexity? [closed]

In computation we always talk about the time and space complexity of a given algorithm. The time complexity describes how long an algorithm takes in relation to the quantity of input it receives. ...
Cybernetic's user avatar
0 votes
0 answers
65 views

kd-tree optimality for orthogonal range search

It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time ...
karmanaut's user avatar
  • 1,177
1 vote
0 answers
47 views

Compute Fourier coefficients from Single Fourier coefficient and initial vector?

I have some vector $\vec v\in\mathbb{Z}_q^n$, and would like to obtain $n$ vectors $\vec f_0,\dots, \vec f_{n-1}$ where $\vec f_i = (\mathcal{F}(\vec v)_i,0,\dots,0)$, i.e. each vector is a single ...
Mark Schultz-Wu's user avatar
1 vote
1 answer
58 views

What is known about the complexity of Network Diversion?

In the Network Diversion problem, we are given an undirected graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with ...
Naysh's user avatar
  • 686
5 votes
1 answer
152 views

Finding $k \times k$ rectangle in a matrix with maximum sum

Given an $n \times n$ matrix $A$ with $0-1$ entries, I want to maximize $\sum\limits_{i \in I, j \in J} a_{ij}$ subject to $|I| = |J| = k.$ I expect the problem to be NP-hard, so I want a polynomial ...
Display name's user avatar
0 votes
0 answers
46 views

Speed networking algorithm

I have 40 people and 10 tables that can accommodate 4 people at a time. The task is to make sure that every person seats with every other person at the same table exactly once, that is every person ...
Helen Grey's user avatar
4 votes
1 answer
88 views

Independent set queries with preprocessing

Suppose we have a sparse undirected graph $G = (V, E)$ with $|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set $A$, is it an independent set in the ...
Command Master's user avatar
1 vote
1 answer
47 views

Maximizing merges with restrictions

Note: The input to this problem has type List[List[List[Pair[int, int]]]]. Since it's tricky to visualize that, I'll use terminology from the original problem, which comes from the optimization of ...
Adam Jamil's user avatar
3 votes
0 answers
88 views

Is the Moser-Tardos algorithm used in any real-world applications?

The Moser-Tardos algorithm can be used to construct algorithms for certain combinatorial problems. However, I'm curious about whether this algorithm is utilized in real-world systems (a SAT solver, ...
Lin's user avatar
  • 31
0 votes
0 answers
92 views

Consequences of early-exiting BFS after reaching the target node in Dinic's algorithm

In a typical exposition (or implementation), Dinic's algorithm executes a full BFS traversal of the residual graph starting from the source node in each phase. If the target node is unreachable, the ...
iheap's user avatar
  • 195
-3 votes
1 answer
137 views

help me understand what semiprime factorizations are worth

Based on a response I received in another post, I would like to ask this question. Are there semiprimes that are not very interesting in terms of research and are not worth factoring? Are only the RSA ...
claudio G's user avatar
1 vote
1 answer
103 views

Exchange cards with sum requirement

Given are positive integers $a_1,\dots,a_{2k},b_1,\dots,b_{2k},S$ such that $\sum_{i=1}^ka_i = \sum_{i=k+1}^{2k}a_i = S$ and $\sum_{i=1}^kb_i = \sum_{i=k+1}^{2k}b_i = S$. There are $2k$ cards, card $i$...
TZM's user avatar
  • 133
1 vote
0 answers
55 views

What are the fastest known parameterized algorithms for Grid Tiling?

Let $k$ and $n$ denote positive integers. In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
Naysh's user avatar
  • 686
-3 votes
2 answers
185 views

pq factorization

If I tried to factor a semiprime as the product of the two prime factors given below in the form pq on a home computer would I be successful? p=(2^1024-1)+644 prime factor q=(2^1028-1)+188 prime ...
user68942's user avatar
0 votes
0 answers
49 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 ...
John_Krampf's user avatar

1
2 3 4 5
37