Theoretical Computer Science Weekly Newsletter - Tuesday, July 29, 2014

Top new questions this week: Are there any cases where quantum has given insight for classical algorithms? To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum … ds.algorithms quantum-computing   asked by hadsed 6 votes answered by Juan Bermejo Vega 9 votes Is generalized pigeonhole search known to be no harder than PPP? Consider the TFNP search problem Given a positive integer $t$ in unary, positive integers $M$ and $N$ (in binary), and a function from $\{0\hspace{.02 in},\hspace{-0.04 in}1,\hspace{-0.03 … search-problem   asked by Ricky Demer 6 votes answered by domotorp 4 votes Is any QMA-intermediate problem known? Similar to the class of classical NP-intermediate problems (e.g. Graph Isomorphism), is there any "QMA-intermediate" problem known, that is in QMA but not known to be QMA-complete? Has this been … quantum-computing np-intermediate   asked by Martin Schwarz 5 votes answered by Niel de Beaudrap 5 votes Type theory for memory safe data structures Data structures such as a doubly linked list and a B+ tree have blocks of memory that have multiple pointers to it. This creates the risk that a bug will allow memory to be accessed after being freed. … pl.programming-languages type-theory linear-logic   asked by user782220 4 votes answered by cody 3 votes Describing state machines mathematically The short paper "Computer Science and State Machines" by Leslie Lamport seems quite strange to me. On the one hand, I am surprised to see that an important hardware protocol called "two-phase … reference-request pl.programming-languages formal-methods examples   asked by hengxin 3 votes extracting/ exploiting similarity of SAT instances by solver suppose that two SAT formulas on different variables $F_1, F_2$ are given on the input that are known to be true and the problem is to build an algorithm that finds a solution to each. the formulas … reference-request sat machine-learning application-of-theory automated-theorem-proving   asked by vzn 3 votes Primitive Recursive Definition : Binary numbers Usually primitive recursive functions are define from Zero, Identity and Successor, projectors, composition and recursion. But you obtain algorithms that works with unary numbers. For example, the … cc.complexity-theory computability   asked by Xoff 3 votes answered by Damiano Mazza 3 votes Greatest hits from previous weeks: Super Mario Galaxy problem Suppose Mario is walking on the surface of a planet. If he starts walking from a known location, in a fixed direction, for a predetermined distance, how quickly can we determine where he will stop? … ds.algorithms cg.comp-geom   asked by JɛffE 111 votes answered by Peter 1 vote Is the traditional analysis of Bloom filters wrong? This paper claims that the traditional analysis of the error rate in Bloom filters is incorrect, then provides a lengthy and nontrivial analysis of the actual error rate. The linked paper was … ds.data-structures   asked by templatetypedef 15 votes answered by Michael Mitzenmacher 35 votes Can you answer these? Automatically Adapting Forgetting Factor for Online EM I've been reading some interesting papers recently on methods for automatically and adaptively setting the learning rate in stochastic gradient descent (SGD). In particular, "No more pesky learning … optimization online-algorithms online-learning   asked by nomad 1 vote Theorem prover fails to find simple set theory proof? I am trying to use an automated theorem prover (SNARK), to prove the following goal, from the following assertions (in first-order logic) - Assertions - The relation 'part of' is transitive. The … lo.logic automated-theorem-proving set-theory   asked by Atriya 1 vote Turing degree of computing definable reals We know that definable real numbers in general are not computable. So what would be turing degree of computing definable real numbers? Would every incomputable definable reals share same turing … computability   asked by Communi 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