All Questions

Suppose that we have an algorithm in which we have a sorted list of objects like $L = (x_1, x_2, \ldots, x_n)$ (the indices denote the order of the objects). During the algorithm we have a loop where ...

In order to empirically test some CSP algorithms, I would like to compile a list of NP-Complete static board games. By static, I mean that a solution of the puzzle is simply an assignment of values to ...

I came up with this problem while thinking about an optimizing compiler. Let $H$ be a hypergraph. From this we construct a graph $G_H$ as follows the vertices are the hyperedges of the hypergraph. ...

It is well known that the pigeonhole principle $PHP_n^{n+1}$ is hard for general resolution. The original proof due to Haken is elegant. One first defines a complexity measure for derived clauses, in ...

A graph with positive edges is given along with several vehicles at specific vertices of the graph.One of the vehicles has a package that is required to be transferred to a destination node.The ...

Suppose we are flipping coins starting at some time $t$. At time $t$ the probability we obtain heads is $\frac{1}{\sqrt{t}}$. If the coin lands tails, at time $t+1$ the probability of heads is now $\...

Given a Graph, where we know Total number of nodes (~100,000) Average no of connections per node (~200) Maximum distance between two nodes (~5) How many nodes (and its connections) do we have to ...

It is well-known that Shannon's channel capacity provides an upper bound on the amount of information (measured in bits/s) that can be reliably (i.e. with vanishing decoding error probability) ...

The class $\textrm{NC}^i$ is the class functions computable by circuits families of bounded fan-in, $n^{O(1)}$ size and $O(\log^i(n))$ depth. The $\textrm{NC}$-hierarchy is the union of those classes....

I am currently dealing with a problem of the following form \begin{alignat}{2} &\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\ &\text{sub to} \hspace{0.05in}&&...

Let $C_4$ be a cycle with four vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>n\sqrt n$, how many $C_4$s exist? Is there a lower bound for this?

From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?) Edit: Perhaps I ...

Suppose we're training a linear separator in the realizable PAC setting. Given $m$ labeled examples $(x_i,y_i)$ in $\mathbb R^d\times\{-1,1\}$, a (consistent) linear separator is a vector $w\in\mathbb ...

I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory. The field seems very interesting for me, but it seems everything is the field was done ...

Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...