The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
2answers
102 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
427 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
179 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
824 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 ...