## 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 ...

computational-geometry

### 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 ...

graph-theory

### 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 ...

interactive-proofs

### 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

### 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 ds.data-structures big-list

### 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

### 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

### 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

### 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 ...

soft-question

### 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

### 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