Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

AC0 closure of Primes

Since Primes is in P by the famous AKS result, the P closure of Primes is just P. Is there anything known about the closure of Primes under weaker reductions? E.g. we know AC0 + mod p is different ...

cc.complexity-theory nt.number-theory  
user avatar asked by Alex W Score of 4

Survey on constructions of $k$-wise independent distributions

I am looking for a good reference discussing different constructions of $k$-wise independent and almost $k$-wise independent distributions. I know the basic constructions using finite fields and low-...

reference-request derandomization proof-complexity k-wise-independence  
user avatar asked by Noel Arteche Score of 2

Is Exact Matching with more than 2 colours NP-hard?

I'm interested in the following problem: given a (multi-)graph with each edge coloured by one of 3 colours, find a perfect matching with exactly k_i edges of colour i in {1,2,3}. I'm also interested ...

np-hardness time-complexity randomized-algorithms matching  
user avatar asked by J. Schmidt Score of 1

Greatest hits from previous weeks:

On the relativization barrier

Baker, Gill and Solovay (BGS) have invented the relativization barrier. They have proven, that there are two oracles $A$,$B$, such that $P^A \not= NP^A$, and $P^B=NP^B$. A solution of $P$ vs. $NP$ ...

cc.complexity-theory oracles p-vs-np relativization  
user avatar asked by Reiner Czerwinski Score of 2

Fastest way to find an s-t min-cut from an s-t max-flow?

Ford-Fulkerson can find sparse s-t flows in time linear in the size of the flow and number of nodes if the edges have unit capacity. How could I use a sparse s-t flow to find an s-t min-cut in time ...

graph-algorithms max-flow max-flow-min-cut  
user avatar asked by Elliot JJ Score of 8
user avatar answered by Magnus Lie Hetland Score of 8

One Stack, Two Queues

background Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...

ds.algorithms ds.data-structures open-problem time-complexity  
user avatar asked by Sadeq Dousti Score of 65
user avatar answered by David Eppstein Score of 48

Why is 2SAT in P?

I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...

cc.complexity-theory np-hardness big-picture polynomial-time  
user avatar asked by Guy Score of 80
user avatar answered by Giorgio Camerani Score of 111

The importance of Integrality Gap

I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real ...

cc.complexity-theory ds.algorithms approximation-algorithms linear-programming integrality-gap  
user avatar asked by Kaveh Score of 52

What kind of answer does TCS want to the question "Why do neural networks work so well?"

My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to ...

machine-learning  
user avatar asked by Neuling Score of 56
user avatar answered by Aryeh Score of 43

How to check if a number is a perfect power in polynomial time

The first step of the AKS primality testing algorithm is to check if the input number is a perfect power. It seems that this is a well known fact in number theory since the paper did not explain it in ...

ds.algorithms nt.number-theory  
user avatar asked by yzll Score of 27
user avatar answered by Ramprasad Score of 35
You're receiving this message because you subscribed to the Theoretical Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy
Stack Overflow

Stack Overflow, 14 Wall Street, 20th Floor, New York, NY 10005

<3