All Questions

Filter by
Sorted by
Tagged with
-2
votes
0answers
15 views

$\mathsf{AC}^0[6]=\mathsf{NC}$ vs $\mathsf{P}=\mathsf{PSPACE}$

$\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{-}\...
0
votes
0answers
14 views

Latest results on the k-stacker crane problem?

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 ...
0
votes
0answers
16 views

Is there a standard definition of resolution for arbitrary clauses?

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 ...
0
votes
0answers
19 views

Creating a random tree (BST) on $n$ elements using a random sequence of zeroes and ones

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 ...
0
votes
0answers
5 views

What is known about the stabilizer rank of this simple state?

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 ...
0
votes
0answers
21 views

Listing Eulerian orienations with special properties

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)$)....
-1
votes
0answers
25 views

How shall backpropagation manage multiple patterns?

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 ...
4
votes
0answers
29 views

Is the following restriction of cellular automata / tile assembly / CRN a known model?

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$, ...
3
votes
0answers
42 views

Precise rank of a sparse integer matrix

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?
4
votes
0answers
40 views

Enumerating results of a variant of LCE queries

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 ...
4
votes
1answer
173 views

Complexity of relaxed edge colouring

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 ...
2
votes
0answers
63 views

When did self-balancing binary search trees become known outside the soviet union?

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 ...
6
votes
0answers
83 views

Decomposing graph homomorphisms

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 ...
-1
votes
0answers
36 views

Bounds on boolean circuit size reduction from fixing input bits

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 ...
0
votes
0answers
32 views

Intuition on context free and other kinds of a forests? Data structures perspective

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 ...
9
votes
1answer
617 views

Ambiguity of regular expressions

Some regular expressions are ambiguous. Some are not. a*b* is unambiguous for example. Expression a*a* is ambiguous but it can ...
1
vote
1answer
125 views

KRW Conjecture: separation of NC^1 and P

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 ...
-2
votes
0answers
40 views

What is the information content of unit tests?

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 ...
1
vote
0answers
89 views

Deterministic one way communication complexity for message with arbitrary length

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 ...
1
vote
0answers
37 views

Generalizing PageRank for tripartite graphs

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]\...
-1
votes
0answers
39 views

Parity game: convert from min odd to max even? [closed]

How does one convert a parity game in the min odd definition to the max even definition?
5
votes
1answer
333 views

Unary language examples between L and NP

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 ...
-3
votes
0answers
29 views

Drawing a Turning Machine from a given function [closed]

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 ...
2
votes
0answers
53 views

Number of connected partitions (or labelings) in a grid graph

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, ...
-1
votes
0answers
37 views

Will A Polydimensional Chess Algorithm Halt? [closed]

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 ...
3
votes
1answer
84 views

Conditioning Probability on a Language With Measure 0

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 ...
1
vote
0answers
79 views

Is there a “common” name for this type of combinatorial optimization problem?

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 ...
1
vote
0answers
43 views

Software tool to generate the Ising model for random $k$-SAT problems

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 ...
-4
votes
0answers
24 views
0
votes
0answers
41 views

Prove that this linear relaxation has half-integral extreme points

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)$...
-1
votes
0answers
36 views

Weak PRG to derandomize BPP into DTIME [closed]

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)))
2
votes
0answers
40 views

Minimal partition covering?

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 ...
-1
votes
0answers
40 views

Error reduction in BPP for other probabilities [closed]

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 ...
-5
votes
0answers
73 views

Please recommend us the appropriate place to consider our paper “The maximum clique problem is solvable in polynomial time by using graph spectrum.” [closed]

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 ...
0
votes
1answer
64 views

Given a partition and an element, find the subset that includes this element

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 ...
-1
votes
0answers
80 views

Are read-once Boolean function in AC^0?

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 ...
0
votes
0answers
48 views

Proof of greedy method to compute minimum Prime Implicant of a monotone Boolean function

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 ...
-3
votes
0answers
77 views

Deciding non-emptiness of a convex polytope via linear programming — request for theorem and proof [closed]

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 ...
0
votes
0answers
33 views

Extension of a sampling Lemma of Indyk for $k$-median cost

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 ...
1
vote
0answers
81 views

Is just one W-type enough for formalizing mathematics?

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 ...
1
vote
1answer
50 views

Weak incidence colouring

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 ...
4
votes
0answers
89 views

Are there any known Chernoff/Hoeffding bounds for the case of “almost independence”?

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 ...
3
votes
1answer
74 views

Algorithm to find $n$ player nash equilibrium

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 ...
2
votes
0answers
122 views

Set-theoretic encoding of functions in type theory

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 ...
3
votes
0answers
72 views

Monotone circuit representations of paths in a graph?

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 ...
5
votes
1answer
184 views

Questions about P vs NP and geometric complexity theory

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 ...
2
votes
1answer
100 views

Solver for uniform matroid isomorphism

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), ...
1
vote
0answers
170 views

anything hinting that EXPTIME $\subseteqq$ PSPACE?

Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$?
2
votes
1answer
105 views

Efficient tools for checking SMT formulas with two quantifiers ($\exists\forall$)

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 ...
4
votes
0answers
65 views

Terminology for languages of pairs of words

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

15 30 50 per page
1
2 3 4 5
226