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

learn more… | top users | synonyms (1)

6
votes
0answers
102 views

Integer queue summation

As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue. The setting is as follows: Let $\epsilon>0$. we need to maintain a ...
12
votes
0answers
183 views
+100

Reference for mixed graph acyclicity testing algorithm?

A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction ...
-3
votes
1answer
95 views

Weighted matching algorithm for minimizing max weight

Consider the following matching problem: Input: a complete weighted bipartite graph with $n+m$ vertices, given by $n$, $m$, and $w_{i}$ a permutation of $[m]$ for each $i \in [n]$. Output: a ...
2
votes
0answers
30 views

Single-pass streaming quantile estimation using moments

Is it possible to estimate within $\epsilon$ the quantiles of a set of integers $\{x_1, x_2, \dots, x_n\}$ given only the values $\sum x_i^0,\sum x_i^1, \sum x_i^2, \dots, \sum x_i^{f(n)}$ where $f ...
1
vote
0answers
168 views

Convex hull of polytopes

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; ...
12
votes
1answer
315 views

Which complexity class does this number theory problem belong to?

'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete. Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?
3
votes
1answer
101 views

Decidability of parametric higher-order type unification

I'm making a language that has higher-kinded types (like Haskell) and allows type synonyms to appear partially applied in type expressions (unlike Haskell). As an example, consider the following ...
1
vote
1answer
98 views

Assignment of values for a set

Consider the following problem: Input: the vertices of two $n$ dimensional axis-parallel cubes: $\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and $\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$. ...
4
votes
1answer
88 views

Polytopes convex hull

Assume $P_1$, $P_2$ and $Q$ are axis-parallel polytopes in $\mathbb{R}^d$. Is it true to say that checking $CH(P_1\cup P_2)\neq Q$ is NP-hard? There is a similar result for the general polytopes but I ...
8
votes
0answers
95 views

Purely Functional Representations of Catenable Sorted Lists question

Good day. I'm currently reading the paper "Purely Functional Representations of Catenable Sorted Lists" by Tarjan and Kaplan[link to the paper]. But I have a question about the modified 2-3 finger ...
4
votes
0answers
190 views

Bit complexity of modulo operations?

We know that using FFT we can compute multiplication of an $a$ bit number with a $b$ bit number in $(a+b)^{1+\epsilon}$ time. My question is supposing we want to compute $A\bmod B$ where $A$ is an ...
2
votes
1answer
71 views

H-representation of convex hull

Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows: $P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
1
vote
1answer
107 views

Is there an efficient program for generating a Sidon sequence?

I would need a Sidon sequence of about $10^9$ elements. I found math papers like [1] that explain how to generate Sidon sequences but it seems a lot of pain to write the corresponding program. Are ...
0
votes
0answers
73 views

Adversarial Search Algorithms

What are the best adversarial search algorithms? I understand that this may seem like a subjective question. However, I am asking for what situations are different algorithms best for. In particular, ...
6
votes
0answers
68 views

Is it possible to unambiguously read back λ terms from interaction nets without node types?

A class of lambda terms can be evaluated using Lamping's abstract algorithm - that is, converting them to interaction nets and applying a set of rules. In order to get the result, you have to read ...
2
votes
0answers
57 views

Claw finding using quantum walk: superposition for Szegedy's framework

Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper: Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices ...
5
votes
0answers
141 views

Is there a linear-time algorithm for max flow on dags

What is the fastest known algorithm for max flow on dags? Can there be a linear-time algorithm running in time $O(|V|+|E|)$? Input: a weighted dag $G=(V,E,w)$ where $E$ is given as an edge list $E$ ...
2
votes
0answers
74 views

Variant of set cover problem with symmetric difference instead of union? [duplicate]

I am wondering if this problem has been studied, and in particular if there is an algorithm for it. Consider a universe $\mathcal U$ and a set $A \subseteq U$, and a family of sets $\mathcal F ...
0
votes
0answers
46 views

Dependency of Algorithms, Data structures on Instruction sets ex: Classical vs Quantum computing

It seems to me that All/any algorithm(s) evolve based on what's feasible on a machine. This is captured within its instruction set. By Analogy data structures are closely associated with physical ...
2
votes
1answer
140 views

Lookup complexity in augmented interval tree

If we consider the following problem: Stream of intervals, coming in one at a time, which we maintain in an augmented interval tree (Interval tree). At some point in time later, we get a point, and ...
2
votes
1answer
96 views

Minimal set of Hyperrectangles covering an n-dimensional binary matrix with row permutations

My input is a n-dimensional binary matrix. My goal is to find the set of Hyperrectangles that covers every '1' at least once and covers not a single '0', which has minimal cardinality (the least ...
7
votes
1answer
179 views

Algorithms for printing the digits of pi, minimizing the time spent between digits

What is the smallest function $t(n)$ such that there exists an algorithm which prints the binary digits of $\pi$, with the time spent between printing digit $n - 1$ and digit $n$ being $O(t(n))$? ...
4
votes
0answers
73 views

Graph factors of maximum weight

I am trying to find references to a weighted version of the graph factor problem for the case when the "target degree" is a set of integers with "gaps" of size at most one. The unweighted version of ...
4
votes
0answers
68 views

How to sample from a distribution with submodular weights

Is there a known algorithm for sampling a set $S \subset \{1,...,n\}$ with probability $p_S = \frac{e^{f(S)}}{\sum_{T \subset \{1,...,n\}} e^{f(T)}}$ where $f: 2^{\{1,...,n\}} \to \mathbb{R}$ is a ...
5
votes
2answers
253 views

What is the application of combinatorial game theory

I find Combinatorial Game Theory very interesting as my primary interest is mathematics. My question is why do Computer Scientists (who tend to have a more practical approach) study it as well? Are ...
4
votes
1answer
158 views

Assignment problem with multiple workers for each job

I am wondering if there are any results on the following version of the assignment problem. We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given ...
4
votes
0answers
75 views

Polynomial Time Delay Enumeration of Maximal Bipartite Subgraphs

Let $G=(V, E)$ be an undirected simple graph. Is it known how to list all the maximal bipartite subgraphs of $G$, without repetitions, and with a polynomial time delay and a polynomial space ...
11
votes
1answer
566 views

Problems with no known quantum advantage

I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer. To start things off, I think computation of ...
1
vote
0answers
55 views

Computing the distribution from which this algorithm samples from

Assume we have a set of integers $X_0=\{x_1\ge x_2\ge\ldots\ge x_n\}$. Let $r\in(0,1]$ be a parameter and consider the ranking process: i=0 while ($X_i\ne\emptyset$) let $M = \max \{x\in X_i\}$ ...
25
votes
1answer
770 views

Finding a biased coin using a few coin tosses

The following problem came up during research, and it's surprisingly clean: You have a source of coins. Each coin has a bias, namely a probability that it falls on "head". For each coin ...
1
vote
1answer
204 views

Sampling distinct values with probability proportional to their frequency

This is a variant of my previous question (Reservoir sampling of distinct values) I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass ...
3
votes
0answers
52 views

Statistical Algorithms vs Convex Relaxations - Planted Clique

I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ? A recent paper by Feldman, ...
5
votes
1answer
149 views

Reservoir sampling of distinct values

I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass through the data is possible. In my case, the stream contains many duplicate values, ...
3
votes
1answer
91 views

Complexity of iterative least squares regression

Given a set of points $P = \{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n) \}$ one can use least squares method to fit a polynomial to $P$. In particular I am interested in linear and quadratic regression. I ...
9
votes
1answer
213 views

Can we construct a k-wise independent permutation on [n] using only constant time and space?

Let $k>0$ be a fixed constant. Given an integer $n$, we want to construct a permutation $\sigma \in S_n$ such that: The construction uses constant time and space (i.e. preprocessing takes ...
-2
votes
1answer
118 views

Is there a mathematical definition of algorithm? [closed]

A friend of mine usually talks to me about Church's thesis. Some days ago I found a proof and talked about it to him. He said that "it's possible to prove the thesis using an arbitrary definition of ...
6
votes
1answer
94 views

Split find-min data structure that finds several small elements?

The split find-min data structure is initialized with a sequence of elements $e_1,\ldots,e_n$, each associated with a key. The data structure supports three operations: (1) $Split(e_i)$ that splits ...
0
votes
1answer
200 views

Enumerating set combinations in an order that maximises the number of previously unseen subsets

Consider a set $S=\{a,b,c,d,e,f,g,h,i,j,k\}$, $\left|S\right|=11$. There are ${11 \choose 5} = 462$ combinations of $S$'s members of size $5$. There are $462! \approx 1.419 × 10^{1032}$ possible ...
14
votes
2answers
1k views

What is known about this TSP variant?

This question was previously posted to Computer Science Stack Exchange here. Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've ...
6
votes
1answer
218 views

Big gaps between RAM and Turing machine complexity

If we only consider problems in P, are there any big gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm for particular problems? I am particularly ...
2
votes
1answer
61 views

List of papers on Runtime and Statistical Tradeoffs on Machine Learning

I was interested in the connection between (statistical) learning guarantees (or any statistical properties) and their relation to run time. For example, I was wondering, in what cases does having ...
4
votes
1answer
211 views

Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?

First of all, I want to make clear that my question is about algorithms. I'd like to know if there are any algorithms with provable guarantees in the context of manifold learning (or manifold ...
3
votes
1answer
184 views

Minimum number of real multiplications to multiply two quaternions [closed]

Karatsuba multiplication of two complex numbers can be performed with just three real multiplications (instead of four) as follows: $$(a+bi)(c+di) = (ac-bd) + i ((a+b)(c+d) - ac-bd)$$ We only need the ...
3
votes
1answer
107 views

What is the best way to find an induced cycle basis of a graph?

My question is essentially what comes in the subject line: what is the best way to find an induced cycle basis of a graph (i.e., a cycle basis of the graph in which each cycle is an induced subgraph ...
0
votes
0answers
51 views

Preventing cycling in the simplex method

In Matoušek and Gärtner's excellent book, Understanding and Using Linear Programming, they discuss various pivot rules and in particular ones designed specifically to avoid cycling. Unfortunately, ...
2
votes
0answers
91 views

Is minimizing sum of distances hard?

The Problem Given a set of $n$ points $S = \{v_1, v_2, \cdots, v_n\} \subset \Re^d$, find a unit vector $s \in \Re^d$ such that $s$ minimizes $$ \sum_{i=1}^{n}\sqrt{\|v_i\|^2 - \langle v_i, s ...
1
vote
1answer
49 views

Far point queries in high dimensions

Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$". This is ...
2
votes
0answers
73 views

Forming Sets from 3-SAT Clauses

I'm wondering if someone can provide a good algorithm for the following problem. If we take 3-SAT in conjunctive normal form, we can partition some or all of the variables (not the literals) into ...
1
vote
1answer
101 views

Lower bound for finding repeated elements in sorted array

This is inspired by [1] (which still needs answers). What is the tight lower bound (or optimal algorithms) for the "finding repeated elements" problem: Given a sorted integer array of size $n$, ...
3
votes
0answers
111 views

Exactly solvable but non-trivial integrality gap

Are there interesting polynomial time solvable problems that we know of for which the natural convex relaxation has a non-trivial integrality gap? Note: Maximum matching doesn't qualify because I ...