Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

Computing 3D viewpoint of a set of non-intersecting segments

Consider the following problem: we are given a finite set of bounded line-segments in ${\mathbb R}^3$, and we want to decide whether there exists a point $p\in {\mathbb R}^3$ from which no two ...

asked by Shaull 4 votes

Known property? Maximum radius of connected induced subgraph

I was wondering if the following graph property has a name and has been researched: Consider any connected induced subgraph $H \subseteq G$. Then $r(G)$ denotes the maximum radius of any such $H$. I ...

asked by Daniel 3 votes

Does the MIP* = RE proof work for limited provers?

MIP* = RE shows that two arbitrarily strong entangled provers can convince a verifier of instances of the halting problem. Now assume that we have two entangled provers that are only capable of ...

asked by Geoffrey Irving 2 votes

Equational Theories for Type Systems

I was reading through Gunter's Semantics of Programming Languages: Structure and Techniques and in the second chapter on simply typed $\lambda$ calculus he introduces an equational theory with ...

reference-request pl.programming-languages type-theory  
asked by Apoorv Ingle 2 votes

Fast Computation of First k Eigenvectors of Graph Laplacian

I'm looking for references for the following; Given the unnormalized Laplacian matrix of a graph $L = D - A, ~ L \in \mathbb{R}^{n\times n}$ Algorithm(s) to efficiently estimate the first $k$ ...

reference-request graph-theory spectral-graph-theory  
asked by Arpit Merchant 1 vote

Greatest hits from previous weeks:

Algorithms from the Book.

Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book. If ...

ds.algorithms soft-question big-list  
asked by Aryabhata 358 votes
answered by Ross Snider 116 votes

Oracle Construction for Grover's Algorithm

In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's ...

quantum-computing quantum-information oracles search-problem black-box  
asked by Will 14 votes
answered by Craig Gidney 18 votes

What are some good introductory books on type theory?

I'm recently studying Haskell and programming languages. Could someone recommend some books on type theory?

soft-question pl.programming-languages type-theory  
asked by qazwsx 28 votes
answered by Steven Shaw 28 votes

What is the logarithm or root operation in type-space?

I was recently reading The Two Dualities of Computation: Negative and Fractional Types. The paper expands on sum-types and product-types, giving semantics to the types a - b and a/b. Unlike addition ...

lo.logic pl.programming-languages type-theory algebra  
asked by efrey 27 votes
answered by pigworker 40 votes

What CS blogs should everyone read?

Many top notch computer science researchers and research groups) maintain active blogs that keep us updated on the latest research in the authors' fields of interest. In most cases, blog posts are ...

asked by Vivek Bagaria 53 votes
answered by Artem Kaznatcheev 41 votes

Major unsolved problems in distributed systems?

Inspired by this question, what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain. Something like membership protocols, data ...

big-list dc.distributed-comp  
asked by zengr 24 votes
answered by Massimo Cafaro 28 votes

Finding the shortest path in the presence of negative cycles

Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the ...

ds.algorithms graph-algorithms shortest-path  
asked by jleahy 13 votes
answered by BlueRaja - Danny Pflughoeft 23 votes
You're receiving this message because you subscribed to the Theoretical Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy
Stack Overflow

Stack Overflow, 110 William Street, 28th floor, New York, NY 10038