# Questions tagged [ds.algorithms]

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

1,577 questions
95 views

### What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?

We know counting perfect matching for bipartite graphs with vertex degree $2$ is in $P$ while counting perfect matching for graphs with vertex degree $3$ is in $\#P$. We also know there are degree $3$...
161 views

### Max-weight connected & co-connected subgraph problem

The max-weight connected subgraph problem (MWCS) may be described as follows: given a simple graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, one seeks for a subset $L\subseteq V$ for which ...
340 views

### Data Structure to calculate which interval a point lies in? [closed]

I have a list of $n$ non-overlapping intervals, namely $[a_1,a_2],[a_2,a_3],...,[a_n,n_{n+1}], a_i \in \mathbb{N}$. Each of these intervals has a corresponding value $v_i$ corresponding to it. Now ...
82 views

### What is known about learning a maximal independent set in a (very) sparse graph?

Maximal independent set is known to be hard in many meanings (hard to approximate, $W[1]$-hard, etc.). But if the number of edges is very small, then the problem becomes simpler. Here, I'm interested ...
95 views

### How to construct an $(n,m,k)$ separating set''?

This problem is probably known under some other name, if anyone has seen it before, a reference will be great. Given $n,m,k$ (for $m,k\ll n$), a $(n,m,k)$ separating set is a set of $n$-sized binary ...
123 views

### Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$...
139 views

### Complexity of $\{0,\pm1\}$ determinant in sparse cases?

If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity? Assume that the matrix ...
269 views

### Complexity of Homogenizing a String

Motivation: While developing tools for data versioning, we ended up looking into algorithms for "diff"ing two sets of integers, by coming up with a sequence of transformations that take one set of ...
69 views

### Finding an answer key given tests and scores

Consider multiple students taking a multiple-choice tests. The test has $q$ questions, and each question has $m$ choices. ($q$ can be large, but $m$ is rather small.) You are given $n$ tests, complete ...
121 views

### Efficiently computing the union of all minimal unsatisfiable constraint sets in a first-order unification problem

Suppose we are given a standard first-order unification problem, represented as a set $D$ of term equality constraints, such that the system $D$ as a whole is unsatisfiable. Consider the minimal ...
83 views

### Is berklemap-massey works on extention field

According to the articles that i read (also wikipedia [1]), they refer that the above algorithm works on finite field $GF(q)$. But I cannot find an evidence that it still works on extension field, i.e:...
49 views

### Counting multiplicative closures

Given a set $S$, its multiplicative closure is the set $$\mathcal{M}(S) = \{s_1s_2\cdots s_k: k\in\mathbb{N},s_i\in S\}$$ of products of zero or more elements of $S$. So the multiplicative closure ...
151 views

### What is known about computing distinct count range queries?

Let $U=\{1,\ldots, u\}$ be a universe of elements for some $u\in \mathbb N$. Given some $n\in\mathbb N$, we are interested in computing some function $f:U^{\le n}\to\mathbb R$ over range queries. In ...
136 views

### Differences with Penalty

Given a sequence $a_1,\ldots,a_n$, find a $k$ and numbers $1\leq i_1< \dots< i_{2k}\leq n$ that maximizes $(\sum_{j=1}^{k}(a_{i_{2j}}-a_{i_{2j-1}}))-2k$. I can get an $n^3$ algorithm using ...
60 views

### Iterative algorithms and Lyapunov functions

Consider an iterative algorithm of the form $x^{t+1} = x^t - \eta g(x^t)$. (..if necessary feel free to assume that a function $L$ is explicitly known such that $g = \frac{\partial L}{\partial x}$..). ...
81 views

### Complexity status of restricted k-clique [closed]

Restricted $k$-clique: Input: $(G,v,k)$ where $v$ is vertex in $V$ Output: k-clique containing vertex $v$. What is the space and time complexity status of this Restricted $k$-clique problem? Is ...
81 views

638 views

### If machine learning techniques keep improving, what's the role of algorithmics in the future?

Let's look at the future some 30 years from now. Let's be optimistic and assume that areas related to machine learning keep developing as quickly as what we have seen in the past 10 years. That would ...
92 views

### Can we make a matrix stable by changing its upper-left submatrix?

A matrix $A$ is called strictly stable if its eigenvalues have negative real parts. Given a matrix $A \in \mathbb{R}^{n \times n}$, suppose we can change its upper-left $k \times k$ submatrix at will (...
111 views

### Factorizing semiprime $n=pq$ with $p \mid q-1$

Could we find a fast integer factorization algorithm for any large semiprime $n=pq$, if we know that $p \mid q-1$?
58 views

### multi-agent pickup and delivery algorithm and conflict resolution

I am looking for a pathfinding algorithm handling the following issues: multiple agents the computed paths for agents may not lead to collisions or deadlocks in space-time a stream of activities ...
28 views

### Sparse coding and matching pursuit algorithms

Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the ...
231 views

### Log space algorithms for modular decomposition tree

Can we have log space algorithms for modular decomposition tree (see definition) for any graph? If not, can we have log space algorithms for modular decomposition tree for any particular graph class? ...
58 views

### What is known about data structures for encoding a set while considering approximate Rank queries?

Consider a universe $\mathcal U\triangleq \{1,2,\ldots n\}$, and assume that we are given a set $S\subseteq \mathcal U$. There are many data structures that allow storing $S$ while answering Rank ...
238 views

### Using an oracle to find a vector $b$ for which $Ax=b$ has a solution

There is an oracle built around a hidden $m\times n$ matrix $A$ all of whose entries are 0 or 1, where $m>n$. The oracle takes as input an integer vector $b$ with positive entries, and answers as ...
214 views

### Why is HyperLogLog (near-)optimal?

The original HyperLogLog paper claims that this probabilistic counting algorithm is "near-optimal". The relevant section of the paper reads: Clearly, maintaining $\epsilon$-approximate counts till ...
2k views

### Theoretical explanations for practical success of SAT solvers?

What theoretical explanations are there for the practical success of SAT solvers, and can someone give a "wikipedia-style" overview and explanation tying them all together? By analogy, the smoothed ...
261 views

### What is the connection between adversarial learning in machine learning and program synthesis?

In particular, I'm considering the similarities in Generative Adversarial Networks and Combinatorial Sketching for Finite Programs. In the first paper, our concern is with learning generator ...
97 views

### Consequence of Decision Tree Complexity of $k$-SUM Problem

Ezra and Sharir showed the $O(n^2\log^2 n)$ linear decision tree complexity for $k$-SUM problem [1], which improves the $O(n^3\log^3 n)$ complexity result of Cardinal et al [2]. It is known that $k$-...
64 views

### Standard basis for recurrence relations

In polynomial algebra there is a powerful tool for treating system of polynomial equations. It is standard or Groebner Bases. It allows to verify if system is consistent, eliminate variables, reduce ...
149 views

### Tight upper bound on the number of iterations of Weisfeiler–Lehman Procedure (Graph isomorphism)

Graph Isomorphism is a very well known problem in computer science. A generic procedure for the graph isomorphism problem builds on a simple color refinement procedure given below (One dimensional ...
202 views

### Complexity of cycle cancellation with integral capacities and irrational costs

Cycle cancellation is a standard textbook algorithm for computing minimum-cost circulations: As long as the residual graph of the current circulation contains a negative cycle, push as much flow along ...
94 views

### Prove np-hard with reduction from scheduling resources [closed]

We have a system in which we have n number of process and m number of resources.The resources are boolean valued that is they can either have value 0 or 1(in brief suppose the resources as single way ...
119 views

### Efficient training algorithm for a generalized version of SVM

In 2014 year we presented a generalized version of the support vector machine that uses family of non-parallel hyperplanes for binary classification. Method easily can be extended to kernel and ...
99 views

### Proof of Correctness of Bottleneck Dijkstra Algorithm [closed]

I am working on a bottleneck multicast tree for which I am using bottleneck Dijkstra algorithm. My question is 1) bottleneck Dijkstra has the same correctness as that of (simple) Dijkstra or not ? 2)...
336 views

### Is there an algorithm which gets incrementally “smarter” as it runs?

Mind the following program: n = 0 best = 0 while (true): if (hash(n) > best): best = hash(n) ++n If you leave this program running for 10 years, when ...
135 views

### Hardness of Subgraph isomorphism problem for sparse pattern graph

Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ ...
362 views

### Worst-case computational complexity of solving Diophantine equation

Manders and Adleman proved that the following decision problem is NP-complete: Given integers $a,b,c>0$, does the quadratic equation $ax^2+by-c=0$ have a solution in integers $x,y>0$? The ...
110 views

### 3-Hitting-Set - maximum flow algorithm [closed]

so i'm currently learning for an exam and got in an exercise the following question (a loose translation): Find an Algorithm that finds the smallest U' ⊆ U that is a solution the 3 HITTING SET ...
### On complexity of permanent ${}\bmod 2^t$?
Valiant showed $\mathsf{Per}(M)\bmod 2^t$ can be computed in $O(n^{4t-3})$ operations where $M\in\Bbb Z^{n\times n}$ holds. Has there been a better algorithm since then?
### On permanent of $\{\pm1,0\}$ matrices
Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|<B$ where $B$ is part of input. Is ...