New answers tagged reference-request
2
Recently, I came across the following survey: Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems
The authors only discuss the major results and mention some interesting open problems at the end.
5
(Just now noticed this question.) There are a lot of questions in the above question. I will try to just address the last few.
Might it be the case that a RAM program can solve general CNF-SAT in exponential time with a base less than 2, but also requiring exponential space, so that when translated to a TM the algorithm runs in exponential time with a base ...
0
It is very hard to define what best means! Anyway, The nature of computation by Cris Moore and Stephen Mertens is very good. The book is nice to either get an introduction to the big ideas of the theory of computation if one is not interested too much in mastering the techniques, or to lift one's head of the track after learning many technicalities. It ...
0
I recommend Math and Computation by Avi Wigderson if you're mainly interested in complexity theory. This is probably best supplemented by other books mentioned in this thread, as it's less rigorous. However the writing is excellent, and would be my go-to for a quick reference or enjoyable read.
0
I recommend "Computability and Logic" by George S. Boolos and John P. Burgess. It's formal, rigorous and fairly thorough. It's a book on computability only, not covering computational complexity.
Notice that some other answers suggested books that focus on computational complexity instead of computability. For instance, (i) "Computational ...
5
Your problem is solvable in polynomial time, as the dimension is fixed (at $d=3$):
Let $h_1,\ldots,h_n$ be an enumeration of all the bounding hyperplanes of the
polytopes $P_1,\ldots,P_k$ and $Q$.
Compute the arrangement of $h_1,\ldots,h_n$ (the subdivision of three-dimensional space into vertices edges, faces, and cells). This can be done in polynomial ...
1
Since the title is about CS and not TCS, maybe an answer about applications of game theory to networking can be of some interest.
Questions about game theory and equilibria arise naturally in networking, since the networks that make Internet are economic competitors and belong to different companies, but they need to collaborate in order to ensure ...
2
There's the TLCA List of Open Problems, collecting unsolved problems in $\lambda$-calculi and related areas, such as proof theory, semantics and theory of programming languages. It is maintained by Ryu Hasegawa, Luca Paolini and Paweł Urzyczyn.
There's also a related list, the RTA list of open problems, concerning rewriting theory. At some point it was ...
3
There is a list of open problems in graph theory and combinatorics collected and maintained by Douglas B. West.
This page maintains a list of lists of open problems in parameterized complexity.
2
In Formal Verification game theory is a recurring theme. I think that one of the most important applications is to define the Simulation Preorder as a game between two players: Spoiler (he) and Duplicator (she). Given a Transition System (in other words, one set $S$ equipped with a labelled transition relation $S \rightarrow S$) Spoiler, starting from a ...
0
One surprising intersection is that of cryptography and game theory.
In cryptography you often want to get rid of trusted parties. For example, imagine some parties wanting to perform a sealed-bid auction—where everybody gives the auctioneer a sealed envelop with a bid inside—but (a) no trusted auctioneer is in sight and (b) the bidders definitely do not ...
4
There is a list of open problems in computational geometry. It is edited and maintained by Demaine, Mitchell, and O'Rourke.
Top 50 recent answers are included
