Top new questions this week: |
||||||||
AC0 closure of PrimesSince 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 ...
|
||||||||
Survey on constructions of $k$-wise independent distributionsI 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-...
|
||||||||
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 ...
|
||||||||
Greatest hits from previous weeks: |
||||||||
On the relativization barrierBaker, 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$ ...
|
||||||||
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 ...
|
||||||||
One Stack, Two Queuesbackground 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 ...
|
||||||||
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? ...
|
||||||||
The importance of Integrality GapI 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 ...
|
||||||||
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 ...
|
||||||||
How to check if a number is a perfect power in polynomial timeThe 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 ...
|
