All Questions

$\mathsf{NC}$ is analogous to $\mathsf{PSPACE}$, $\mathsf{TC^0}$ is analogous to $\mathsf{PP}$ and $\mathsf{ACC^0}$ is analogous to $\mathsf{MOD}_\mathsf{k}$. If $$\mathsf{DLOGTIMEUNIFORM}\mbox{-}\...

I was searching for the $k$-stacker crane problem on google scholar but the best known result is dated back to 1976 with the original paper. I'm unsure whether there would be newer results of the ...

Knuth defines in [1] a resolution operator for arbitrary clauses which sets $C = C' \diamond C'' = (C' \lor C'')$ when there is no literal $x$ such that $x \in C'$ and $\neg x \in C''$. I skimmed over ...

We have a sorted list of $n$ numbers and we shall create a BST for these numbers. We create a random sequence of zeroes and ones of length $n$. We shall make use of this random binary sequence to form ...

Consider the uniform superposition of all length-$n$ bit-strings of Hammming weight $w$, $$ |\phi_w\rangle =\sum_{x\in \{0,1\}^n,|x|=w} |x\rangle$$ What is known or conjectured about the stabilizer ...

An orientation of a simple undirected graph is said to be Eulerian if every vertex has the same number of in-coming edges and out-going edges (i.e., in-degree($v$)=out-degree($v$) for all $v\in V(G)$)....

There is an algorithm taken from this source which implements calculation of a gradient of the cost function for each weight in a neural network: This algorithm happened to do well. We can subtract ...

Consider the following model: we work in the $d$-dimensional grid $\mathbb{N}^d$, and we have an alphabet $\Sigma$. The initial cell $(0,\ldots,0)\in \mathbb{N}^d$ is marked with some letter $\Sigma$, ...

Consider a large sparse rectangular integer matrix. Is there a way to compute its exact rank that is better in terms of speed and/or memory usage compared to a dense matrix?

Let $\Sigma$ be an ordered finite alphabet. Longest Common Extension (LCE) queries are the following problem: Input: a string $w$ of size $n$ Query: two integers $i$ and $j$ such that $0 < i \leq ...

A (proper) $k$-edge colouring of a graph $G(V,E)$ is a function $f:E\to\{1,2,\dots,k\}$ such that adjacent vertices are mapped to different colours; that is, $f(e)\neq f(e')$ if $e$ and $e'$ are ...

According to wikipedia, the AVL tree was first published in 1962 by Soviet scientists Adelson-Velsky and Landis. The earliest self-balancing binary search tree I can find by a non-soviet block ...

A homomorphism $h: G\to H$ from a graph $G$ to a graph $H$ is a function from the vertices of $G$ to those of $H$ which preserves edges, that is, if $(x,y)$ is an edge of $G$ then $(h(x),h(y))$ is an ...

Given some boolean circuit $C$ on $n$ input bits, how much can the size of $C$ (defined as the number of non-input gates) decrease if $k$ of those inputs are fixed in value, resulting in a new circuit ...

I am trying to gain intuition on formal forests, also called tree languages, i.e., sets of trees. There are regular tree languages, and there are context free tree languages. They both come in a ...

Some regular expressions are ambiguous. Some are not. a*b* is unambiguous for example. Expression a*a* is ambiguous but it can ...

More than a real question this is a recap of something I have been studying. I hope someone will help me getting things straight, so any correction or thought about the following reasoning is more ...

Suppose I have a piece of code which solves a quadratic equation. I solve $x^2 -1 = 0$ using my code, and I verify that it spits out $x_0 = 1$, $x_1 = -1$. I've learned something from that, and ...

Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message. I have been looking into ...

Problem I have the following directed tripartite graph $G(E\cup V\cup P, A)$, where there is a many-to-one symmetric relationship between the subsets V and E - $e\in E,v\in V,[e, v]\in A \iff [v, e]\...

How does one convert a parity game in the min odd definition to the max even definition?

I am looking for some examples of unary languages lay between $L$ and $NP$, i.e., $ L \subseteq NL \subseteq P = AL \subseteq NP $. What I found after some search(e.g., Complexity zoo for unary ...

If we have 4 variables (a, b, c, d) equal to any unary numbers, how could we construct a Turing Machine that adds these 4 variables together, i.e. a+b+c+d. I am very confused on this and I appreciate ...

Let $G$ be a 2D lattice graph (undirected) of size $W\times H$. Each "inner" vertex has $4$ adjacent vertices, whereas "boundary" vertices have $2$ or $3$ adjacent vertices, ...

I'm trying to train a clade of evolutionary algorithms to play chess in n-dimensions, where n is finite but arbitrarily large. Unsurprisingly, I may be evolving results that do not halt. Clearly, the ...

Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you ...

I'm trying to find papers that discuss approaches (in particular, any Deep Learning or Deep Reinforcement Learning techniques) that could be used used to solve the problem described in the next ...

Is there a software tool available to study the phase transition of the underlying Ising model for a given class of random $k$-SAT problems? I am basically asking whether the framework presented in ...

I have question. How can I do that ? ...

Given a graph $G=(V,E)$, here is a Linear Relaxation of the edge cover polytope: (1) For each $v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$ (2) For each $e \in E$, $0 \leq x_e \leq 1.$ Here $\delta(S)$...

Assuming there is a deterministic polynomial time TM M such that on every input 1^m, outputs a((log m)^2, m, 1/10)-PRG. Please show that BPP ⊆[c>1DTIME(2^((log n)^c)))

I am working on a problem that arises in the design of experiments. I wonder if it is part of a well-studied class of problems. The problem is: Start with a set of points $S$ and a target partition of ...

Can someone please explain how the error reduction is done in BPP? Moreover, if • if x ∈ L, then Pr[M(x) = 1] ≥ 4/5; • if x 6∈ L (x does not belong to L) , then Pr[M(x) = 1] ≤ 3/5; How can I prove L ...

We showed that the maximum clique problem solvable in polynomial time by using a graph spectrum we developed. I submit our paper, editor rejects promptly without reading its body. If someone knows of ...

I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am ...

A Boolean function is said to be read-once if there is a Formula (a Boolean circuit where every gate has fanout at most $1$) computing the function $f$ such that every variable appears only once in ...

The decision version of Prime Implicant problem is NP-complete for Monotone Boolean function. I present below a greedy algorithm to find the minimum prime implicant ( minimum number of variables which ...

I'm trying to make an algorithm for deciding the feasibility of the polyhedron: $$Ax = b, \quad x \geq 0$$ Can I solve the following optimization problem to determine if my polyhedron has any ...

A famous sampling lemma of Indyk (Theorem 31 here) states that if the $k$-median cost of a finite point set(in a metric space) is large with respect to the optimum, then this is true for the case of a ...

We work in intensional Martin-Löf type theory with $0$, $1$, $2$, $\Pi$, $\Sigma$, $W$ and a cumulative hierarchy of universes. Suppose our goal is to formalize constructive mathematics. Now if we ...

Let $G(V,E)$ be a simple undirected graph, let $k\in \mathbb{N}$, and let $I(G)=\{(v,e)\ :\ e\in E, v\in e \}$ (here, $v\in e$ means $v$ is incident on $e$). A $k$-incidence colouring of $G$ is a ...

The usual statement of a Hoeffding bound (e.g. https://sites.math.washington.edu/~morrow/335_17/ineq.pdf) requires independent random variables. My question is: Do there exist bounds similar to ...

This is the question asked 10 years before. Most of the algorithm and software mentioned are out of date. I am wondering is there new approchs for this problem in the last 10 years? The game dealing ...

Functions usually get encoded in set theory as follows. A function $A\to B$ is a subset $f\subset A\times B$ such that $\pi_1:f\to A$ is a bijection. In type theory to give a function $A\to B$ is to ...

Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every ...

Reading through various papers on geometric complexity theory (GCT), there is one thing, which pops up, while claimed in various places, that it is an approach to P vs NP, all the results seems to ...

I want to solve the following coNP-complete problem efficiently in practice: Given a linear matroid represented as $k \times n$ matrix over a finite field $\mathbb{F}_p$ (where $p$ is large prime), ...

Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？

I would like to check a sort of SMT formulas with two quantifiers where universal variables range over finite/bounded integer domains. An example formula is $$\exists x \forall y ((y \ge 1 \land y \le ...

I want to consider $L \subset A^* \times B^*$ as a "language". Is there standard terminology for this? I wrote "double language" first (but that doesn't sound right to me), then &...