Theoretical Computer Science Weekly Newsletter - Tuesday, December 30, 2014

Top new questions this week: Problems in $\mathsf{BPP}$ not known to be in $\mathsf P$? What problems are known to belong to $\mathsf{BPP}$ but not known to belong to $\mathsf P$? More precisely, I am interested in independent problems, that is whose derandomizations are not known to be ... derandomization   asked by Bruno 18 votes answered by Peter Shor 9 votes Complexity of n-queens-completion? The classical $n$-queens problems asks, given a positive integer $n$, whether there is an array $Q[1..n]$ of integers satisfying the following conditions: $1\le Q[i] \le n$ for all $i$ $Q[i] \ne ... cc.complexity-theory board-games   asked by JɛffE 10 votes Hartmanis-Stearns conjecture and the computable transcendental numbers Hartmanis and Stearns have a conjecture (Hartmanis, J.; Stearns, R. E. (1965), "On the computational complexity of algorithms", Transactions of the American Mathematical Society 117: 285–306) that ... cc.complexity-theory reference-request examples   asked by XL _at_China 8 votes answered by Yuval Filmus 8 votes Finding a median in a union of sets given as sorted arrays You are given $k$ sorted arrays $A_1, A_2, ..., A_k$, each containing $n$ elements. How fast can you compute the median of $A_1 \cup A_2 \cup ... \cup A_k$ ? I have a solution running in ... ds.algorithms time-complexity   asked by R B 6 votes What's the upper bounds for #3-SAT circuits? We have, from this thread on 3-SAT upper bounds, and this answer on #P that the current best upper bounds for 3-SAT is faster than $O(1.31)^n$, and approximately $O(1.64^n)$ for #3-SAT. Can we do ... sat upper-bounds   asked by Matt Groff 6 votes How Univalence can be used for proofs about algorithm correctness I read a book on homotopy type theory. HoTT has the univalence axiom. This axiom seems to simplify working in category theory, but which other fields of mathematics it simplifies? I.e. how can I use ... type-theory homotopy-type-theory   asked by Konstantin Solomatov 5 votes answered by Andrej Bauer 7 votes Why does the transformation in the proof for SL=L preserve connectedness of s and t? I'm currently working on this paper showing that $\mathcal{SL} = \mathcal{L}$. But I keep wondering how the transformation $\tau$ in definition 3.1 preserves the connectivity of $s$ and $t$. $\tau$ ... graph-theory graph-algorithms derandomization   asked by Dave 4 votes answered by Yuval Filmus 3 votes Greatest hits from previous weeks: Are research papers hard to read? This question may not suit to here, but I couldn't find a better place to ask (it was closed in SO). I find research papers on computer science hard to understand. Of course the subjects are ... soft-question research-practice   asked by nimcap 57 votes answered by David Eppstein 120 votes What is the contribution of lambda calculus to the field of theory of computation? I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with ... soft-question big-picture lambda-calculus ho.history-overview   asked by PhD 60 votes answered by Martin Berger 71 votes Can you answer these? Formalizing Homotopy Type theory in Idris Looking at the homotopy type theory blog one can easily find a lot of library formalizing most of Homotopy Type Theory in Agda and Coq. Is there anyone aware if there is any similar attempt to ... proof-assistants homotopy-type-theory   asked by Giorgio Mossa 3 votes Realization of a bipolar orientation by a mixed graph Given an undirected graph $G(V,E)$ and a bipolar orientation $s$ over $G$, consider the problem of identifying $s$ by finding the minimum number of edges such that when orienting them in a particular ... graph-theory graph-algorithms directed-acyclic-graph   asked by seteropere 1 vote What is the standard name for the function which inflates a string by duplicating each of its characters? Given a string $s$ over some alphabet, I'd like to use the proper nomenclature/notation for the operation/function $f$ which inflates $s$ by independently duplicating each of its characters. For ... co.combinatorics string-matching combinatorics notation   asked by Yann Ponty 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