The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
1answer
325 views

Would an optimal sorting network ever have to swap two numbers the “wrong” way

Intuitively it seems like an optimal (either minimum depth or minimum gates) sorting network should never have to compare-swap two numbers the "wrong" way (such that the larger one goes into the ...
4
votes
0answers
79 views

Splay tree potential function: why sum the logs of the sizes?

I'm teaching a course on data structures and will be covering splay trees early next week. I've read the paper on splay trees many times and am familiar with the analysis and intuition behind the data ...
2
votes
2answers
108 views

How are PCPs and ZKPs related?

I only have a (very) introductory knowledge about the Hardness of Approximation and PCP theorem, and I am wondering if it has any specific implications (or can somehow be studied) with Zero Knowledge ...
1
vote
1answer
513 views

Primal vs dual decomposition methods

I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I ...
2
votes
1answer
221 views

An intuitive justification - Metric Embedding Based Approximation Algorithms

Recently, I started (independent) learning of the theory of metric embeddings from the Fall 2003 course offered at CMU . I had a very basic question from the very first lecture of this course ...
12
votes
5answers
871 views

Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?

It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$. This can easily be understood inductively using oracle machines. The question ...
25
votes
6answers
1k views

How do you get a “Physical Intuition” for results in TCS?

I'm sorry if this question is a little vague, but I am curious how successful researchers get a "feel" for the results in TCS. For example, linear algebra can be understood geometrically, or in terms ...