Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [ds.algorithms]

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

7
votes
1answer
187 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, ...
3
votes
1answer
108 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
votes
0answers
55 views

greedy performance

I have a set function $f:2^V\rightarrow R_+ $which is non negative monotone supermodular function with a property that $f(\{x\})$ is same for all $x\in V$($f(\{x_1\})=f(\{x_2\})=\dots =f(\{x_i\}),\...
1
vote
1answer
68 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 ...
11
votes
0answers
170 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
2answers
75 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 ...
1
vote
0answers
33 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
116 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 ...
2
votes
0answers
33 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 ...
6
votes
1answer
217 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, ...
1
vote
1answer
75 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$ ...
3
votes
0answers
54 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 $...
6
votes
0answers
141 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)&...
1
vote
0answers
7 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 $\...
5
votes
0answers
162 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
65 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 ...
0
votes
1answer
110 views

Permuting the columns of a 0/1-matrix to avoid short segments

Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment ...
5
votes
0answers
115 views

Evaluating addition chains

I hope this is a suitable place to ask this question. An addition chain of size $n$ is a sequence $x_1, \dots, x_n$, where $x_1$ is fixed to 1 and $x_i = x_j + x_k$ for some $j,k < i$. I am ...
1
vote
0answers
33 views

PTAS for projective clustering : survey

$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $k$ $j$-flats in $\mathbb{R}^d$ that minimizes the cost function as defined below: Given a $j$-...
-4
votes
2answers
81 views

Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]

Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted. (notice how many times the 2 is touched [circled in red ...
5
votes
1answer
65 views

Pop desired elements on stacks of bounded capacity

Consider there are $k$ stacks containing a total of $n$ elements. Each element is either red or blue. We have complete knowledge of each element's location and color. Only push and pop are allowed on ...
-1
votes
1answer
59 views

Formally prove that the loops of this sorting algorithm will terminate [closed]

Given is the sorting algorithm Bubblesort ...
5
votes
1answer
226 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 ...
2
votes
1answer
74 views

Find shortest prefix to generate original string by overlapping

Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed). For ...
1
vote
0answers
119 views

How to write algorithms?

Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to"...
2
votes
1answer
99 views

Minimization version of matrix p-norms?

I considered a minimization version of matrix p-norms, defined for a matrix $A$ by $$ f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}. $$ Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
1
vote
0answers
22 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 ...
17
votes
1answer
2k views

Algorithm whose running time depends on P vs. NP

Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
6
votes
2answers
253 views

Algorithm for identifying unprovable statements

I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms? For example: If there ...
8
votes
2answers
263 views

Non-Orthogonal Vectors Problem

Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
2
votes
0answers
80 views

On the goal of learned clause database reduction in CDCL SAT solvers

Modern SAT solvers frequently reduce the size of their learned clause database in order to keep its size as manageable as possible. This has as effect not to slow down the speed of unit propagations. ...
5
votes
0answers
106 views

Lower bound for enumerating k closest pair of points

Consider 1 dimensional points $x_1, \dots x_n, x_i \in \mathbb{R}$ where the distance between any two points is defined as $d(x_i, x_j) = \vert x_i - x_j \vert$. The goal is to enumerate all $n^2$ ...
10
votes
1answer
308 views

Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons

Is there a comparison-based sorting algorithm that uses an average of $\mathrm{lg}(n!)+o(n)$ comparisons? Existence of a worst-case $\mathrm{lg}(n!)+o(n)$ comparison algorithm is an open problem, but ...
3
votes
0answers
46 views

Lower bound for reversing a list using queues

How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues? Each queue is FIFO. Time refers to the number of operations on the queues. ...
8
votes
0answers
124 views

Finding $n$ many different primes efficiently

I want to find $n$ many different primes on RAM. I can find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ in $O(n)$ running time. A brute force way is to find $O(\frac{n}{\log n})$ many ...
14
votes
1answer
1k views

Deciding whether an interval contains a prime number

What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the ...
1
vote
0answers
217 views

Impagliazzo lemma, unclear detail in its proof

In Arora-Barak's book on page 378 in the proof of Impagliazzo's Hard Core lemma why did they choose the number 50 in this line: Set $t = \frac{50n}{\epsilon^2}$ ? How this choice then yields the size ...
5
votes
1answer
131 views

What does “hold uniformly” mean in the context of asymptotic analysis?

What does "hold uniformly" mean in the statement of Theorem 1.7 in A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):
4
votes
1answer
177 views

Fast algorithm to find a maximum connected subgraph of k vertices

Given an undirected graph $G = (V, E)$ and a function $f: 2^V \to \mathbb{R}^+,$ where $2^V$ is the set of all subsets of $V$. Find a connected subgraph $T = (V_T, E_T)$ of k vertices such that $f(V_T)...
1
vote
0answers
55 views

Minimization of the maximal adjacent integer sums on a circle

Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? For specific and low $n$'s it has been pointed out in math.stackexchange....
2
votes
1answer
101 views

What is the best approximation and exact algorithm for vertex cover on cubic graphs?

"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
6
votes
1answer
150 views

How to solve this generalization of binary search?

Let $f:\{1,\ldots,n\}$ be a monotonically non-decreasing function. Consider, for some unknown threshold $1\le T\le n$, a threshold function $$g(x)= \begin{cases} 0&\text{x<T}\\ 1&\text{...
3
votes
1answer
48 views

Complexity of distributively verifying that the diameter is small

Consider a graph $G=(V,E)$ and an integer parameter $k$. I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ...
4
votes
0answers
69 views

2-hop distributed coloring in the CONGEST model

Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$. A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \...
2
votes
0answers
208 views

Career advice needed: Switching from theoretical CS to pure math

I couldn't think of a better forum to ask this question. I am a first year cs graduate student. I couldn't really pursue theoretical cs during my undergrad, but as part of our PhD qualifiers, i had to ...
2
votes
1answer
229 views

Existence of an algorithm

I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting ...
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 ...
3
votes
1answer
47 views

Algorithm for finding smallest set and instanciation for a given constraint system

I have a system of constraints described by a set of clauses of the form $x_1 \neq x_2 \lor \dots \lor x_{i-1} \neq x_i$, for instance: ...
21
votes
4answers
803 views

Problems that are counter-intuitively solvable in practice?

Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in ...
0
votes
1answer
96 views

How can algorithms with nested combinatorial searches be quasi-linear?

I've come across algorithms similar to the one below, where a demanding step is performed, which should have at least polynomial complexity, yet the whole algorithm is deemed quasi-linear without ...