# All Questions

12,409 questions
Filter by
Sorted by
Tagged with
55 views

### computational complexity of sparse matrix powers

Given a sparse matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in it. What is the computational complexity of computing $A^k$, for some positive integer $k$? As $k$ gets larger, I ...
86 views

### Does ${\bf CPO}$ have $\omega$-colimits?

Does the category ${\bf CPO}$ have $\omega$-colimits? By ${\bf CPO}$ I mean the category that has as objects the $\omega$-complete pointed partial orders and as arrows $\omega$-continuous functions.
89 views

### Reductions and projections in circuit complexity

I'm struggling to find a good reference that defines the difference between projection and monotone projection in the context of Boolean functions and circuit complexity. My understanding is that a ...
266 views

### Is $PSPACE$ believed to be different than $PP$?

From Googling, I couldn't find any discussion about whether $PP=PSPACE$ is more or less likely than $PP\subsetneq PSPACE$. Is it currently believed that $PP\neq PSPACE$? What would be the ...
65 views

68 views

### In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$

I am reading Depth Reduction of Arithmetic Formula form the survey of Ramprasad Saptharishi. Now in the proof of depth reduction due to Brent, 74 that Let $f$ be an n-variate degree d polynomial ...
29 views

### Distribution-free learning vs distribution-dependent learning

I asked this question on Mathoverflow and realized that it should have been better to ask here. My main confusion is, how to distinguish distribution-free learning and distribution-dependent learning ...