## 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
 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
 asked by Sidharth Ghoshal Score of 2
 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
 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
 asked by ULechine Score of 1
 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
 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
 asked by Aaron Sterling Score of 151
 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
 asked by hawkeye Score of 52
 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
 asked by Lev Reyzin Score of 140
 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
 asked by Akash Kumar Score of 66
 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
 asked by kodlu Score of 22
 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
 asked by Rui Liu Score of 6
 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
 asked by vb le Score of 32
 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, 110 William Street, 28th floor, New York, NY 10038

 <3