Questions tagged [ds.algorithms]

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

1,594 questions
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$?
68 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 ...
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 ...
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? ...
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 ...
239 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 ...
269 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 ...
100 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 , which improves the $O(n^3\log^3 n)$ complexity result of Cardinal et al . It is known that $k$-...
65 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 ...
156 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 ...
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 ...
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 ...
104 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)...
339 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 ...
140 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|)}$ ...
375 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 ...
165 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 ...
218 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?
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 ...
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 ...
264 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$, ...
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 ...
263 views

205 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 ...
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 $... 1answer 161 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 ... 0answers 124 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 ... 1answer 144 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 ... 1answer 314 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 ... 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 ... 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 ... 1answer 1k views Is the 2016 implementation of Shor's algorithm really scalable? In the 2016 Science paper "Realization of a scalable Shor algorithm" , the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of  and Table 5 ... 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 ... 1answer 158 views Complexity of counting maximum number of co-linear points in Euclidean plane The problem: given a set of points in the Euclidean plane, find the maximum number of co-linear points. I already know that the problem can be solved in quadratic time using hashing or projective ... 1answer 112 views Base extension in residue number systems with low space Suppose I have a number$x$represented in a residue number system, so$x = (x_1, \ldots, x_m)$, where$x_i \equiv x \pmod{p_i}$, and the$p_i$'s are all relatively prime (they can be distinct primes ... 1answer 323 views Pattern matching with don't cares: multiple patterns Kalai's 2-page SODA paper gives a simple and efficient algorithm for pattern matching with don't cares (wildcards that match one character). In essence, it is as easy as convolution. But what happens ... 0answers 294 views Complexity of$k=2$set packing I am interested in the best currently known algorithm (in fact, any relevant reference) for the following problem: Given a family of subsets$S_1,S_2,\ldots S_N\subseteq \{1,2,\ldots N\}$, ... 0answers 79 views Constant time Lookup for Inversion Problem I'm trying to figure out how to compute all the significant inversions$(i,j)$in a list$l = [a_1, \ldots a_n]$where an inversion$(i,j)$is significant if$i < j$but$a_i > 2a_j$. Now there ... 1answer 283 views Free books (or course materials) on undergraduate algorithms What free books (or course materials) are there that cover undergraduate algorithms material? I added "course materials" in case there exist comprehensive sets of lecture notes/video/other that are ... 1answer 248 views Complexity involving connected components of 0/1 matrix Assume a matrix has one component means we can traverse from a matrix entry$(i,j)$which is$1$to any other one by moving step of$(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$where each step you take you ... 1answer 232 views Find a string with minimal edit distance from a set of given strings Input: a bunch of binary strings: x_0, x_1, ... , x_n Output: a binary string y that minimizes edit(x_0, y) + edit(x_1, y) + ... edit(x_n, y) where edit(x, y) denotes the levenshtein distance, i.e. ... 1answer 330 views Fast Algorithm to Check if a Set of Sets forms an Anti-chain Given a set$S$of sets, what is the fastest algorithm to check if elements of$S$form an anti-chain with respect to subset ordering? That is, how can I quickly decide if there exists two sets$A$... 1answer 279 views Are there poly time algorithms to determine if a graph is almost bipartite? Given an undirected graph G, we can say that G is almost bipartite if deleting k edges (or vertices) would make it bipartite. Are there poly time algorithms to determine if a graph is exactly or ... 1answer 247 views For a given binary-search tree obtain an isomorphic splay tree I will assume that the reader is familiar with some undergraduate algorithms and data structures. To people who are not familiar with splay trees I recommend to read through this link : https://en.... 1answer 279 views Enumerating all simply typed lambda terms of a given type How can I enumerate all simply typed lambda terms which have a specified type? More precisely, suppose we have the simply typed lambda calculus augmented with numerals and iteration, as described in ... 2answers 727 views Memory requirement for fast matrix multiplication Suppose we want to multiply$n \times n$matrices. The slow matrix multiplication algorithm runs in time$O(n^3)$and uses$O(n^2)$memory. The fastest matrix multiplication runs in time$n^{\omega + ...
Suppose I have a boolean circuit $C$ that computes some function $f:\{0,1\}^n \to \{0,1\}$. Assume the circuit is composed of AND, OR, and NOT gates with fan-in and fan-out at most 2. Let \$x \in \{0,...