Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

Relationship between two graph optimization problems

Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph: P1. Find a largest induced subgraph of the ...

graph-algorithms np-hardness np-complete  
asked by Andras Farago 7 votes
answered by Antti Röyskö 14 votes

Constraints on sliding windows

Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer. I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...

automata-theory complexity streaming-algorithms sliding-window  
asked by C.P. 5 votes
answered by Denis 2 votes

Complexity of finding the largest induced subgraph with all even degrees

What is the complexity of the following problem? Instance: Simple, undirected graph $G$, and a positive integer $k$. Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that ...

graph-theory graph-algorithms np-complete  
asked by Andras Farago 5 votes

Is there a notion of "sequential" idempotence?

TL;DR: I have a definition, and I'm wondering if it already has a name or has been studied. Suppose we have a sequence of operations (or if we want to be mathematical, functions whose domains and ...

asked by Dan Staley 3 votes
answered by J.-E. Pin 2 votes

Covering a set of moving points with two disks of same size

The best algorithms for the following problem has $O(n^2 \log{n})$ running time: Given a set $P$ of $n$ points in $\mathbb{R}^2$ and a real parameter $r$, can we cover all the points in $P$ with two ...

np-hardness computational-geometry covering-problems  
asked by Rafi 2 votes

If $P=BPP$, then Is it correct that $IP=NP$?

This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, ...

derandomization interactive-proofs  
asked by user777 2 votes
answered by Joshua Grochow 8 votes

How hard is it to approximate distance of linear code

I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance. I of course found that ...

np-hardness approximation-hardness coding-theory  
asked by Bartolinio 2 votes

Greatest hits from previous weeks:

Guidelines to reduce general TSP to Triangle TSP

I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie: $D(a, b) \leq ...

cc.complexity-theory np-hardness np tsp hamiltonian-paths  
asked by Dave 6 votes
answered by Kristoffer Arnsfelt Hansen 21 votes

What kind of answer does TCS want to the question "Why do neural networks work so well?"

My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to ...

asked by Neuling 52 votes
answered by Aryeh 38 votes

Difference between weak duality and strong duality?

For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different: Weak duality: If $\bar{x}$ ...

ds.algorithms optimization linear-programming primal-dual  
asked by mtahmed 3 votes
answered by Ilan Kom 7 votes

Intuitively, why is the complementary slackness condition true?

What's an intuitive proof that shows that the conditions of complementary slackness are indeed true: If $x^*_j > 0$ then the $j$-th constraint in the dual is binding. If the $j$-th constraint in ...

ds.algorithms linear-programming primal-dual  
asked by PhD 7 votes
answered by Rahul Savani 14 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 13 votes
answered by Craig Gidney 17 votes

Why is 2SAT in P?

I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...

cc.complexity-theory np-hardness big-picture polynomial-time  
asked by Guy 55 votes
answered by Giorgio Camerani 88 votes

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