The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
156 views

Quantum algorithms and quantum computation

Is my (very high-level) understanding correct here regarding quantum algorithms — Quantum computers can process a massive amount of operations in parallel to the nature of qubits and their ...
-2
votes
1answer
63 views

proof of convergence in arbitrary precision PRNGs

consider a program that generates a random walk using a PRNG, as in following pseudocode. it uses arbitrary precision arithmetic such that there is no limit on variable values (ie no overflow). ...
2
votes
1answer
66 views

Electrical resistance of expander graphs

Let $G$ be a $d$-regular expander graph. What is the electrical resistance of $G$? Is it a constant independent of the number of nodes $n$ once $d$ is large enough? If not, can we give matching upper ...
2
votes
0answers
83 views

Graph conductance - program/code/library

Technical question: is there any open source program/code/library which can compute (minimal) conductance of a given graph, probably by some simulated annealing? Think it is quite well-known problem, ...
2
votes
1answer
82 views

Increasing entropy of random walk

Let $P$ be a transition matrix of a random walk in an undirected (may not regular) graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by $$H(\pi)=-\sum_{v \in ...
3
votes
1answer
182 views

How many random walks to start from each node?

Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of ...
12
votes
1answer
240 views

On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
1
vote
1answer
161 views

Prove: cover time for directed graph is exponential

How can I prove that the cover time for a directed graph G can be exponential in the size of G?