Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

Deciding if all matrix multiplication entries have at least two witnesses

Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N×N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C=AB$ (not boolean matrix multiplication but the ...

ds.algorithms lower-bounds matrices  
user avatar asked by karmanaut Score of 3

Are there any problems whose best known algorithms have running time $n^{\log \log n}$?

It’s well known that problems such as integer factorization have running times contained in $e^{\text{Poly} \log }$ which is the same $n^{ \text{Poly} \log }$ (actually the log term is itself in a ...

complexity-classes time-complexity  
user avatar asked by Sidharth Ghoshal Score of 2
user avatar answered by Robert Andrews Score of 4

Efficient enumeration of connected functional digraphs (up to isomorphism)

Together with the research intern I am supervising, we are currently writing some software that requires us to enumerate all connected functional digraphs of $n$ vertices up to isomorphism (also known ...

cc.complexity-theory ds.algorithms graph-algorithms graph-isomorphism enumeration  
user avatar asked by Antonio E. Porreca Score of 1

Can polynomial sized DNF be used to construct weak PRF

Let $F_x : \{0;1\}^n \rightarrow \{0;1\}$ be a family of polyomially sized DNF (with respect to $n$). The key $x$ lives in $\{0;1\}^{\lambda(n)}$, $\lambda(n)$ is polynomially bounded in $n$. Can such ...

pseudorandomness cryptography  
user avatar asked by ULechine Score of 1
user avatar answered by AnonTCS Score of 0

The tree augmentation problem, but with hyperlinks

In the (Weighted) Tree Augmentation Problem, we are given a tree $T = (V,E)$ and a set of additional edges $L$ called links with non-negative costs. Each link $\ell = (u,v)$ covers the tree edges ...

reference-request graph-theory co.combinatorics approximation-algorithms optimization  
user avatar asked by Karagounis Z Score of 1

Greatest hits from previous weeks:

What videos should everybody watch?

Stanford University now has a Youtube channel, with free access to HD video of full courses on everything from dynamical systems to quantum entanglement. More conferences and workshops are ...

soft-question big-list  
user avatar asked by Aaron Sterling Score of 151
user avatar answered by Mikhail Glushenkov Score of 55

Relationship between Turing Machine and Lambda calculus?

Is there a relationship between the Turing Machine and the Lambda calculus - or did they just happen to arise about the same time?

computability lambda-calculus turing-machines  
user avatar asked by hawkeye Score of 52
user avatar answered by Charles Stewart Score of 34

Problems Between P and NPC

Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...

cc.complexity-theory np-hardness big-list np-intermediate  
user avatar asked by Lev Reyzin Score of 140
user avatar answered by Lev Reyzin Score of 113

The origin of the notion of treewidth

My question today is (as usual) a bit silly; but I would request you to kindly consider it. I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...

graph-theory co.combinatorics big-picture ho.history-overview treewidth  
user avatar asked by Akash Kumar Score of 66
user avatar answered by Paul Seymour Score of 65

Implications of proving NP=RP on complexity theory

Edit: As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, ...

cc.complexity-theory np  
user avatar asked by kodlu Score of 22
user avatar answered by usul Score of 22

Difference between syntax and semantic error in programming languages

When compilers generate errors for a specific programming language, there's distinction between syntax & semantic errors. E.g. ) + f 3 has ill-formed syntax, ...

pl.programming-languages semantics parsing compilers  
user avatar asked by Rui Liu Score of 6
user avatar answered by cody Score of 7

Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ ...

cc.complexity-theory soft-question big-picture p-vs-np physics  
user avatar asked by vb le Score of 32
user avatar answered by Peter Shor Score of 59
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, 110 William Street, 28th floor, New York, NY 10038