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

learn more… | top users | synonyms (1)

1
vote
0answers
10 views

Purely Functional Representations of Catenable Sorted Lists question

Good day. I'm currently reading the paper "Purely Functional Representations of Catenable Sorted Lists question" by Tarjan and Kaplan[link to the paper]. But I have a question about the modified 2-3 ...
0
votes
0answers
19 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
51 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
96 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
68 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, ...
-3
votes
0answers
34 views

Which are the areas where Audio Compression is used? [closed]

I have chosen a project on 'Data Compression' for my final year B.Tech project. I was initially thinking about doing works on Image compression then going to Video compression and work there. But my ...
6
votes
0answers
64 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
54 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
133 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
44 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
138 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
94 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
173 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
71 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
64 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 ...
4
votes
0answers
140 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
150 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
558 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
54 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
757 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
168 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
51 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
143 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
81 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
210 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
117 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
93 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
197 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
216 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
60 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
199 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
183 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
103 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
50 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
90 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
72 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
100 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 ...
3
votes
1answer
115 views

Rate of convergence for the Perron–Frobenius theorem

The Perron–Frobenius Theorem states the following. Let $A = (a_{ij})$ be an $n \times n$ irreducible, non-negative matrix ($a_{ij} \geq 0, \forall i,j: 1\leq i,j \leq n$). Then the following ...
2
votes
1answer
67 views

How to simulate sequential registers from causal ones?

Background: In distributed shared memory (DSM) model, the problem of register simulations/constructions is to simulate registers with certain characteristic out of registers with weaker features. For ...
10
votes
2answers
477 views

Fun with inverse Ackermann

The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: http://www.gabrielnivasch.org/fun/inverse-ackermann. $$\alpha_1(n) = [n/2]$$ $$\alpha_2(n) = ...
0
votes
1answer
62 views

Finding intersections of numerically implemented 1-dimensional curves on a 2-dimensional plane

Question summary: what are the known efficient algorithms to find the intersections of 1-dimensional curves living on a 2-dimensional plane? Detail: I have a set of 1-dimensional curves on a ...
8
votes
0answers
153 views

Speed-up of Boolean over Algebraic computation

I would like to know what is the maximum speed-up of algebraic computation when we work in the word RAM model. This question is motivated by this theorem from Ryan's paper: Theorem 1.2 Let $(R, ...
0
votes
0answers
75 views

Efficient generation of Tournament Graphs

How to generate all non-isomorphic tournament graphs of order $n$ in an "efficient" way ? nauty (http://cs.anu.edu.au/~bdm/nauty/) can generate non-isomorphic tournaments, what is the complexity of ...
12
votes
5answers
542 views

Additive combinatorics applications in algorithm design

I'm reading surveys by Trevisan and Lovett on applications of additive combinatoric in TCS. The majority of these applications fall under computational complexity, e.g., lower bounds. I wonder if ...
3
votes
1answer
90 views

Lower bounds for inversion counting in comparison model?

For counting the number of inversions in an array, there are many $O(n \log n)$ algorithms, e.g. the one that modifies Merge Sort. There is an easy $\Omega(n)$ lower bound simply because you have to ...