User András Salamon - Theoretical Computer Science Stack Exchange

András Salamon

Member for 13 years, 8 months
Last seen more than 2 years ago

constraints.wordpress.com
Edinburgh, UK

113 Answers

Score Activity Newest

4 votes

When is relaxed counting hard?

answered Oct 10, 2010 at 13:57

6 votes

Finding the penumbra of a Constraint Satisfaction Problem

answered Oct 6, 2010 at 22:02

32 votes

Accepted

Where do I turn for help with research/publishing?

answered Oct 6, 2010 at 22:57

25 votes

Accepted

Circuit lower bounds over arbitrary sets of gates

answered Oct 2, 2010 at 14:43

6 votes

Accepted

Using SAT for Computer Vision tasks

answered Oct 2, 2010 at 15:54

2 votes

Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?

answered Sep 30, 2010 at 10:49

-2 votes

Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?

answered Sep 27, 2010 at 20:13

7 votes

Simple question about decision problems

answered Sep 28, 2010 at 17:54

7 votes

Accepted

Separation of limited nondeterminism classes?

answered Sep 26, 2010 at 17:35

18 votes

Problems Between P and NPC

answered Sep 27, 2010 at 21:19

10 votes

Is there a candidate for a natural problem in $P/poly - P$?

answered Sep 25, 2010 at 21:31

18 votes

Dinner-table description of theoretical computer science?

answered Sep 20, 2010 at 0:36

12 votes

What papers should everyone read?

answered Sep 16, 2010 at 17:17

3 votes

Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results

answered Sep 16, 2010 at 13:40

22 votes

Accepted

What does one mean by heuristic statistical physics arguments?

answered Sep 13, 2010 at 2:33

5 votes

In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.

answered Sep 4, 2010 at 16:24

12 votes

Are there alternatives to using polynomials in defining the different notions of efficient computation?

answered Aug 24, 2010 at 22:02

8 votes

Graph families which have polynomial time algorithms for computing the chromatic number

answered Aug 24, 2010 at 13:38

41 votes

Major unsolved problems in theoretical computer science?

answered Aug 23, 2010 at 16:29

3 votes

Alternate notion of complexity based on gap between brute-force and the best algorithm?

answered Aug 20, 2010 at 17:49

13 votes

References for TCS proof techniques

answered Aug 19, 2010 at 2:47

23 votes

What are good references to understanding the proof of the PCP theorem?

answered Aug 17, 2010 at 0:16

5 votes

What specific evidence is there for P = RP?

answered Aug 16, 2010 at 23:36

4