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
0answers
61 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}$..). ...
0
votes
1answer
83 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 ...
3
votes
0answers
90 views

Restricted k-set cover is in NL or L

Restricted $k$-set cover: Input: $(U,S_1,S_2,\cdots, S_n, k)$, $U=[n]$ and $S_i\subseteq U$ for all $1\leq i \leq n$. Output: $\bigcap_{i\in I}S_i$ where $I=\{1,i_1,i_2\cdots,i_k\}, i_1=min(S_1),i_2=...
1
vote
0answers
81 views

Off-policy Monte Carlo Control

The off-policy Monte Carlo control algorithm to learn the optimal state-value function $V^*$ is given as follows, which is obtained from Sutton's book. I have three questions concerning this ...
6
votes
1answer
139 views

Merging Graph Edges to form a 2 color-able Graph (with weight constraints)?

Given an undirected graph $G$. Each vertex has a weight 1. We define shrinking an edge as merging and replacing 2 adjacent vertices $(A, B)$ with a new vertex $C$ such that all the vertices that were ...
3
votes
0answers
99 views

Notion of “total work” of a problem?

I apologize in advance if this question is outside the scope of this Exchange community; if so, perhaps someone can point me in the right direction. I am curious if there is a theoretical notion of "...
5
votes
1answer
122 views

Reference request: complexity of $k$-partite $k$-SAT

Let's consider following variation of $k$-SAT that I will call $k$-partite $k$-SAT: given $n$ variables that are divided into $k$ groups and a $k$-SAT formula $\phi$ such that each clause has literal ...
3
votes
1answer
117 views

Necessary and sufficient number of comparisons by every element to fully sort a set of n elements? [duplicate]

Given $n$ distinct elements. Is there a sorting algorithm which ensures that every element is compared atmost $\lg n$ time? Or is there a higher lower bound?
-3
votes
1answer
178 views

Is finding a solution harder than verifying a solution? [closed]

Is there any known problem in Comp science where determinisitically finding a "non-trivial" solution to that problem is asymptotically easier than verifying a solution?
7
votes
1answer
171 views

Rank-robustness of the parallel complexity of linear algebra problems

It is known that most computational problems related to linear algebra can be computed in $NC^2$ - i.e. for an $n\times n$ matrix $A$, over the reals or a finite field, we can compute the rank of $A$, ...
0
votes
1answer
98 views

Reachability in Dynamic Line Graph

Given a directed line graph $G = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$, there are two operators, namely $\mathsf{move}(v_i, v_j)$: this operator moves $v_i$ to the position ...
3
votes
0answers
250 views

A sequence wherein the Kolmogorov complexity of the terms does not increase

I am looking for an algorithm $A$ - which for any non-null input string $s_1$ produces a sequence $s_1, s_2...$ such that : It can be proved in some axiomtic system $S$ that: $\...
23
votes
2answers
676 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 ...
1
vote
0answers
94 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 (...
3
votes
0answers
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$?
1
vote
0answers
71 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 ...
1
vote
0answers
31 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 ...
5
votes
2answers
232 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? ...
1
vote
0answers
59 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 ...
7
votes
1answer
242 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 ...
5
votes
0answers
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 ...
42
votes
5answers
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 ...
-1
votes
1answer
271 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 ...
7
votes
0answers
101 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$-...
2
votes
0answers
66 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 ...
4
votes
0answers
161 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 ...
10
votes
0answers
208 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 ...
2
votes
0answers
97 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 ...
1
vote
0answers
105 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)...
6
votes
2answers
340 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 ...
4
votes
1answer
141 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|)}$ ...
6
votes
0answers
392 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 ...
-2
votes
1answer
178 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 ...
5
votes
1answer
219 views

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?
5
votes
0answers
198 views

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 ...
-1
votes
1answer
109 views

Multiple source shortest path with one reversal [closed]

Lets say we have a directed graph G, with vertices V, that have lengths l. I need to find the shortest path between every ordered pair of vertices in the graph, with the following constraint: In a ...
7
votes
1answer
268 views

How much memory is needed for counting distinct elements in a stream exactly with high probability

Assume we know a parameter $n\in\mathbb N$, and then get to observe a sequence of elements $x_1,\ldots, x_n$, one at a time. Our goal is to count the number of distinct elements in $x_1,\ldots, x_n$, ...
2
votes
2answers
100 views

Constructing integer sets in which a certain equation has no solution

Given some linear equation, e.g., $$x+2y=3z+4u+5w,$$ I would like to construct a set $S$ of $n$ positive integers so that equation has no solution in $S$. Two questions: 1) How big must the integers ...
3
votes
3answers
268 views

A subset grouping problem

I'm trying to reduce the following problem to a more well-known formulation. I have a bunch of subsets $\{S_i \}_{i \in I}$ of some finite set. I would like to put them into (disjoint) groups $\{ ...
3
votes
3answers
319 views

Pairwise comparison of bit vectors

Define a partial order $\le$ on $\{0,1\}^d$ by pointwise comparison, i.e., we say $x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,d$. I am interested in the following problem: Given $x_1,\dots,x_n \...
0
votes
2answers
209 views

Circle graph algorithm

You are given N points on 2-D plane. How can I find out minimal radius of a circle which contains at least M of these points? algorithm for code I searched for smallest enclosing circle problem but ...
2
votes
1answer
170 views

Efficient enumeration of the reachable leaves of nodes in a polytree

A polytree is a directed acyclic graph which does not have any undirected cycles, i.e., it is a tree when we replace each directed edge by its undirected counterpart. Given a polytree $T$ and a node $...
4
votes
1answer
162 views

Algorithms in preprocessed universe [closed]

In celebrated paper Clustered integer 3SUM via additive combinatorics by TM Chan and M Lewenstein one of the provided algorithms is the one for preprocessed universe. They were able to provide an ...
5
votes
0answers
127 views

Online triangle counting

Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs. Given a graph $G$ and a collection $C$ of subsets of ...
1
vote
1answer
145 views

How to find the “best vectors” in a given matrix whose sum of products is as small as possible?

The input is a matrix $\mathbf{A}=[a_{ij}]$ of real numbers $a_{ij}>0$ for all $i\in\{1,\ldots,k\}$ and $j\in\{1,\ldots,n\}$ and a real number $v$. The coefficient of the matrix are not all greater ...
6
votes
1answer
320 views

Understanding proof of Theorem 3.3 in Karp's “Probabilistic Recurrence Relations”

Background: In Karp's paper on Probabilistic Recurrence Relations, he develops tail-bounds for random variables satisfying the following recurrence: $$ T(x) = a(x) + T(h(x)) $$ where $T(x)$ is a ...
1
vote
0answers
174 views

Maximize the weight of MST + sum of vertex weights

I am considering a problem where the goal is to choose a subset of size $k$ of the vertices in a graph, such that the weight of their minimum spanning tree + the sum of their vertex weights is ...
5
votes
1answer
188 views

Finding a positive point for a collection of polynomials

I am wondering about the complexity of the following problem: Given $k$ polynomials $p_1(x_1, \ldots, x_n)$, $p_2(x_1, \ldots, x_n)$, $\ldots$, $p_k(x_1, \ldots, x_n)$ over the $n$ real ...
23
votes
1answer
1k views

Is the 2016 implementation of Shor's algorithm really scalable?

In the 2016 Science paper "Realization of a scalable Shor algorithm" [1], the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of [2] and Table 5 ...
6
votes
0answers
160 views

Positive cut algorithm on bipartite graphs with negative weights

Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...