Skip to main content

Questions tagged [analysis-of-algorithms]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
18 votes
1 answer
2k views

Polynomial speedups with algorithms based on semidefinite programming

This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time. I am still puzzling over the actual running time of algorithms that compute the solution of ...
Alessandro Cosentino's user avatar
10 votes
2 answers
3k views

Random walk and mean hitting time in a simple undirected graph

Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges. I'm trying to determine the expected running time of Wilson's algorithm for generating a random spanning tree of $G$. There, ...
arekolek's user avatar
  • 311
8 votes
2 answers
360 views

Given a subset of the hypercube and a copy translated by s, find s

Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...
boinkboink's user avatar