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

Top new questions this week: Complexity of the coset intersection problem Given the symmetry group $S_n$ and two subgroups $G, H\leq S_n$, and $\pi\in S_n$, does $G\pi\cap H=\emptyset$ hold? As far as I know, the problem is known as the coset intersection problem. I am … cc.complexity-theory gr.group-theory   asked by maomao 13 votes answered by Joshua Grochow 7 votes What separates easy global problems from hard global problems on graphs of bounded treewidth? Plenty of hard graph problems are solvable in polynomial time on graphs of bounded treewidth. Indeed, textbooks typically use e.g. independet set as an example, which is a local problem. Roughly, a … graph-theory graph-algorithms treewidth   asked by Juho 13 votes answered by Daniel Marx 9 votes Correctness proofs of classic Paxos and Fast Paxos I am reading the "Fast Paxos" paper by Leslie Lamport and get stuck with the correctness proofs of both classic Paxos and Fast Paxos. For consistency, the value $v$ picked by the coordinator in phase … ds.algorithms dc.distributed-comp proofs   asked by hengxin 8 votes answered by Michael Deardeuff 6 votes Reasoning about NP$_{\mathbb{R}}$ Using the real-RAM/BSS model, we have the class NP$_{\mathbb{R}}$, (where a BSS is the Blum-Shub-Smale model of a computer with operations over reals). We have NP$_{\mathbb{R}}$ complete problems. … cc.complexity-theory computing-over-reals   asked by user27305 7 votes answered by Joshua Grochow 5 votes Purely functional uniquely-represented deques There are a number of purely functional deques that support $O(1)$ operations at each end. None that I know of are "uniquely represented" - deques with the same number of items can have different … ds.data-structures functional-programming   asked by jbapple 6 votes References for de-amortization I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against … reference-request ds.data-structures lower-bounds amortized-analysis   asked by rahulmehta95 5 votes Ref question: K-nearest neighbours in a graph Given an undirected graph $G$ with $n$ vertices, $m$ edges, and positive weights on the edges, I am interested in the problem of computing for each vertex the $k$ distinct vertices in $G$ that are … reference-request shortest-path   asked by Sariel Har-Peled 5 votes answered by Marzio De Biasi 2 votes Greatest hits from previous weeks: Books on automata theory for self-study I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams. reference-request automata-theory fl.formal-languages   asked by user1652 25 votes answered by Sadeq Dousti 30 votes 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 110 votes answered by Mikhail Glushenkov 38 votes Can you answer these? Limits of parallel computing with local connections? There are successes with an increasing numbers of individual computational units in GPUs or as processor cores. Given someone made the effort to build a huge array of processors which - however - can … time-complexity dc.parallel-comp   asked by Gerenuk 1 vote Problems in dynamic algorithms in computational geometry The publication of Chiang and Tamassia's paper on dynamic algorithms in computational geometry included several algorithms used in solving dynamic computational geometry problems such as: Dynamic … cc.complexity-theory ds.algorithms cg.comp-geom   asked by q2liu 4 votes Online bridge and nonbridge counting (identification) I was wondering if there is any efficient (possibly armortized poly-logarithmic) online algorithm which supports counting (identification) of bridges- and non-bridges online, i.e. during a sequence of … ds.algorithms graph-theory dynamic-algorithms   asked by antarcticfox 3 votes

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