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

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

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

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

terminology

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

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

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

## Greatest hits from previous weeks:

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 ... machine-learning  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

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

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

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