Questions tagged [ds.algorithms]

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

3
votes
1answer
57 views

What is the maximal load of a “latency-bounded” Cuckoo Hash?

Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time. They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is ...
0
votes
1answer
109 views

Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?

1) Let $A$ be a (general purpose) algorithm that factors $n$. Suppose $A$ contains a loop (which is hard to imagine if not impossible that it does not.) If $A$ contains nested loops then these loops ...
17
votes
3answers
769 views

Computing sum of sparse polynomials squared in O(n log n) time?

Suppose we have polynomials $p_1,...,p_m$ of degree at most $n$, $n>m$, such that the total number of nonzero coefficients is $n$ (i.e., the polynomials are sparse). I am interested in an efficient ...
0
votes
0answers
79 views

Is it possible to sort by only knowing the sign of pairwise sums?

I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this ...
-3
votes
0answers
27 views

minimum cost spanning tree algorithm with benchmark graphs

I have developed one minimum cost spanning tree algorithm. How can I check the algorithm with benchmark graphs?
5
votes
1answer
329 views

Solving “all-marginals” problem for independent sets on grid

Suppose I have a distribution over independent sets on an $n\times n$ grid where the probability of independent set occupying nodes $(i_1,j_1),\ldots,(i_k,j_k)$ is proportional to $\lambda_{i_1,j_1}\...
1
vote
1answer
86 views

How many samples are needed to reconstruct a path?

Consider an input set of vertices $V$ and vertices $s,t\in V$. The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be ...
3
votes
2answers
869 views

Subset-sum-difference problem

Consider the following problem: SUBSET-SUM-DIFFERENCE: Let $S=\{s_1,\dots,s_n\}$ be a set of $n$ integers and $t$ be a "target" integer. Are there two disjoint subsets of $S$ (call them subsets $I$ ...
0
votes
0answers
45 views

Mapping of entire balls using Locality Sensitive Hashing (LSH)

LSH functions are useful for approximate nearest neighbor search. They are usually defined, for distance metric $d$ and $c>1$ as follows: A family of hash functions is $(r, cr, p_1, p_2)$-LSH ...
3
votes
0answers
215 views

Convention for RAM machine models

When algorithm asymptotic runtimes are given without explicitly noting the computational model, what is the convention for the exact model used? My understanding is that most problems use unit-cost ...
5
votes
0answers
157 views

Is there a fast algorithm for inverting a sparse matrix?

I am doing research on a random-walk like problem. As a critical part of my solution, I need to invert a non-singular sparse matrix of size $n \times n$ and with $O(n)$ non-empty entries. I'm working ...
8
votes
1answer
353 views

What is the hardest instance for the group isomorphism problem?

Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, ...
7
votes
2answers
180 views

Determining how n-tuples are sorted as you search them?

I have a sorted list of $N$ n-tuples, but I do not know exactly how they were sorted. The person who sorted them did so by lexicographically ordering some permutation least-to-greatest. For example, ...
-1
votes
1answer
50 views

How is additive error handled in this simple algorithm? 'Product of all elements'

Say we have two unit vectors $\hat{u}, \hat{v} \in \mathbb{R}^n$ where $\hat{u} = (u_1,...,u_n)$ and $\hat{v}$ approximates $\hat{u}$. $~\hat{v} = (u_1+\epsilon, ...,u_n+\epsilon)$ where $\epsilon = \...
5
votes
0answers
244 views

Practical algorithm for testing whether an edge is Delaunay

I have a set of vertices $V\subset\mathbb R^3$ and a set of edges $S=\{(a,b)|a,b \in V\}$. I want to know whether an edge in the set $S$ is Delaunay against the vertices in $V$. My assumed ...
4
votes
1answer
624 views

Knapsack with dependent profits (pairs of items)

I'm working on a problem which MAY be reduced to the following version of Knapsack: Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in ...
2
votes
1answer
60 views

In external memory, is grouping equal elements easier than sorting?

Sorting an array will put equal elements adjacent to each other. So, in no model of computation can grouping equal elements be harder than sorting. In the RAM model, grouping equal elements is $O(n)$ ...
30
votes
10answers
2k views

Great algorithms, machine learning and no linear algebra

I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of ...
2
votes
1answer
76 views

Longest stack-sortable subsequence

Given an array of $n$ pairwise-different positive integers, the problem is to find the longest subsequence that is stack-sortable, i.e. avoiding the permutation pattern $231$. How fast can this ...
17
votes
1answer
458 views

Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does ...
24
votes
5answers
5k views

What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the ...
34
votes
1answer
1k views

Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "packing" ...
2
votes
0answers
101 views

Shortest s-t path when is allowed to ignore k weights

Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed ...
2
votes
0answers
48 views

Complexity of comparing extended integer power towers

Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by ...
2
votes
0answers
78 views

Finding 3SUM witness when promised a solution

Suppose we have a 3SUM instance given with the promise that there exists at least one solution. Is the trivial $O(n^2)$ (modulo logarithmic improvements) solution still the best algorithm or is there ...
4
votes
0answers
96 views

Arranging letters to make a word in a regular language

Fix a regular language $L$ on the alphabet $\{a, b\}$, and consider the following problem. I am given as input: some number $m \in \mathbb{N}$ of copies of the letter $a$, and some number $n \in \...
1
vote
0answers
76 views

Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

Has anyone studied the asymptotics of problems in complexity classes like $BPP$? The thought came to me that if a problem in $BPP$ only requires $O(log(n))$ bits of entropy to solve then, intuitively, ...
5
votes
1answer
120 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 ...
3
votes
1answer
129 views

How is SDP an extension of spectral algorithms?

In one of his lectures, Uri Feige described semidefinite programming (SDP) as ... an algorithmic technique that extends both linear programming and spectral algorithms. I know the basic ...
1
vote
1answer
74 views

The SQ argument in Balazs Szorenyi's paper

I am asking about the proof in Theorem 5 (page 6) of this paper, http://www.inf.u-szeged.hu/~szorenyi/Cikkek/sq_d0_ext.pdf Quite a few things about this short argument seem unclear to me, Towards ...
1
vote
2answers
83 views

Enumerate all allocations of points in a simplex

Consider the standard 2-simplex $\{(x,y)~|~x+y=1~;~ x,y\geq 0\}$. Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y by the following process: Fix two positive ...
11
votes
0answers
176 views

Computational Complexity of the Frobenius Problem

The Frobenius problem takes as input $n$ positive integers $a_1,\ldots,a_n$ with $\gcd(a_1,\ldots,a_n)=1$ and asks for the largest integer $F$ that cannot be written in the form $F=a_1x_1+a_2x_2+\...
1
vote
0answers
36 views

Minimising the maximum distance to the centre of a cluster of points

I have a set of points $C_i$ on a two dimensional plane and I want to find a point $P$ such that the maximum distance from $P$ to any of the points is minimised, i.e. minimise(max($||P-C_i||$)). I've ...
2
votes
1answer
121 views

Generalizations of linear programming

Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs. Is there a survey/lecture notes describing ...
6
votes
1answer
229 views

Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)

In the wikipedia article on Time Complexity it is written that: The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, ...
2
votes
0answers
36 views

Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in ...
116
votes
11answers
10k views

How hard is unshuffling a string?

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a ...
13
votes
1answer
448 views

Fast sparse boolean matrix chain product

So, I've got about 100-200 very sparse square boolean matrices with side length ~several dozens, and I need to compute their product. I know that if I multiply them serially, the product will usually ...
1
vote
1answer
76 views

About learning a single Gaussian in total-variation distance

I am looking for the proof of this following result which I saw as being claimed as a "folklore" in a paper. It would be helpful if someone can share a reference where this has been shown! Let $G$ ...
5
votes
1answer
230 views

Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

Let $(X,+,\cdot)$ be a commutative ring. Let $|\cdot|\colon X\to \mathbb{N}$ be a function that satisfies $|x+y|\leq |x|+|y|$ and $|xy|\leq |x|+|y|$. We call the function length, and length is always ...
0
votes
1answer
550 views

What does “number of inputs to each neuron” mean in Neural Network terms? [closed]

I am reading about a Neural Networks project that has some data like this I am new to this, and though I think I understand what a 3:1 network mean, I do not understand what number of inputs (to each ...
7
votes
1answer
106 views

Smoothed analysis to compare algorithms

Has there been any research using smoothed analysis to compare approximation algorithms that have the same approximation ratio? Any research that compares algorithms using smoothed analysis would be ...
6
votes
0answers
149 views

Bottleneck $k$-link path in a complete DAG

Let $G$ be a complete DAG: It has vertices $v_1,\ldots,v_n$, and $v_iv_j$ is an edge if and only if $i<j$. Let $w(i,j)$ be the weight of the edge $v_iv_j$. The weight has the property that $w(i,j)&...
2
votes
0answers
55 views

Conjugacy testing problem

The below-given problem is in black box setting means input is given by set of generators. Given an abelian $p$-group $A$ and two matrices $U_1$ and $U_2$ in $R(A)$ such that the order of $U_1$ and $...
1
vote
0answers
10 views

Size of solutions in integer programming

Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
6
votes
3answers
305 views

Linear Time Maximum Clearance Computation on a Grid Graph?

I have a uniform NxN grid with a non-empty subset of vertices marked as obstacles. My goal is to compute, for each non-obstacle vertex, the "maximum clearance" from the obstacle set. In other words, ...
29
votes
1answer
1k 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 ...
5
votes
0answers
169 views

What's the fastest known algorithm for finding the diameter of a graph?

Given a positively weighted graph what's the fastest algorithm for finding the diameter for that graph?
2
votes
0answers
67 views

What is the competitive ratio of a $d$-way associative LRU cache?

In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$. It is well known that for ...
20
votes
4answers
1k views

Positive topological ordering, take 3

Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix? This question is motivated by this problem: Positive topological ordering ...