Theoretical Computer Science Weekly Newsletter - Tuesday, April 28, 2015

Top new questions this week: Can we not output the Kolmogorov complexity? Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on ... cc.complexity-theory kolmogorov-complexity universal-computation universal-turing-machines   asked by domotorp 11 votes What would signify hierarchy collapse to first level? We know that $$\mathsf{NP\subseteq P/Poly \iff coNP\subseteq P/Poly\implies PH=\Sigma_2^P}=\mathsf{\Pi_2^P}$$ $$\mathsf{NP\subseteq P/Log\iff coNP\subseteq P/Log\implies PH=\Sigma_0^P=\Pi_0^P}$$ ... cc.complexity-theory circuit-complexity   asked by Turbo 8 votes Complexity of algebraic problems I am looking for a list about complexity of various numerical/algebraic problems. E.g. $GCD\in NC^1$ is open. factoring is in $P$ is open. computing sheaf cohomology is $\#P$-hard. [Arora and ... cc.complexity-theory big-list algebra open-problem   asked by Turbo 7 votes answered by Joshua Grochow 11 votes Is there a program for theory of incompleteness in $NP$? Motivated by Suresh's post, Techniques for showing that problem is in hardness limbo, it seems that there might be an underlying theory that explains why some of these problems can not be complete for ... cc.complexity-theory   asked by Mohammad Al-Turkistany 7 votes Dimensionality reduction in machine learning This is less of a question and more of a "here's my take let me know if you agree" (so I guess it might turn into a big-list?). Dimensionality reduction refers to a collection of techniques that ... machine-learning lg.learning   asked by Aryeh 5 votes answered by Nikos M. 1 vote Do these set systems imply a partition? During research, I hit a set theoretic claim that I could neither proof nor disproof. Let $S_1,S_2,S_3$ be three set systems over the same finite universe $U$ such that $S_1,S_2,S_3$ are ... set-system   asked by Oliver Witt 4 votes answered by domotorp 3 votes Matching problems that are easy for bipartite graphs but hard for general graphs Are there variants of matching problem (decision or optimization problem) that are polynomial time solvable for bipartite graphs but are NP-hard for general graphs? graph-algorithms matching   asked by Hans 3 votes answered by Hiroki Yanagisawa 0 votes 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 113 votes answered by Mikhail Glushenkov 39 votes What is the difference between propositions and judgments? I get confused by the subtle difference between propositions and judgments when exposed to intuitionistic type theory. Can any one explain to me what is the point to distinguish them and what ... lo.logic pl.programming-languages type-theory   asked by day 22 votes answered by Anthony 15 votes Can you answer these? Is there a typed lambda calculus which is consistent and Turing complete? Is there a typed lambda calculus where the corresponding logic under the Curry-Howard correspondence is consistent, and where there are typeable lambda expressions for every computable function? This ... type-theory lambda-calculus typed-lambda-calculus curry-howard   asked by Morgan Thomas 3 votes Coset state of $3$-node graph isomorphism problem The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should ... quantum-computing graph-isomorphism physics gr.group-theory quantum-walk   asked by Omar Shehab 1 vote

Subscribe to more Stack Exchange newsletters Unsubscribe from this newsletter or change your email preferences by visiting your subscriptions page on stackexchange.com. Questions? Comments? Let us know on our feedback site. If you no longer want to receive mail from Stack Exchange, unsubscribe from all stackexchange.com emails. Stack Exchange, Inc. 110 William St, 28th Floor, NY NY 10038 <3