All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
19 views

Abstract stone duality and cohesive homotopy type theory

I have been reading the real-cohesive homotopy type theory paper and one of the remarks has sparked an interest. In this paper a string of monadic and comonadic modalities is introduced together with ...
2
votes
0answers
31 views

What are some “must-read” papers for someone getting into Quantum Cryptography?

I'm a graduate student that just finished a first course on quantum computation. I've also done a graduate-level course in (classical) cryptography. I'm interested in Quantum Cryptography and would ...
5
votes
0answers
58 views

How to find the second smallest cut in a graph?

For an undirected graph, how do we find the second smallest $s,t-$cut(s) for some $s,t\in V$? What's the time complexity of this computation? What if we only cared about finding a cut of size $p+1$, ...
-4
votes
0answers
32 views

Consequence of $CLS=PPAD\cap PLS$

https://arxiv.org/abs/2011.01929 claims $CLS=PPAD\cap PLS$ and it is appearing in http://acm-stoc.org/stoc2021/accepted-papers.html (STOC $2021$) which bolsters its validity. Is there implications to ...
1
vote
0answers
17 views

Efficiency of building orthogonal range search structures?

I've been reading up on data structures for 2D range searching. I've noticed that, in many of the papers I've read, there's close attention paid to the query cost and the space usage required, but ...
3
votes
1answer
132 views

Proof and computational complexity

I couldn't find documents elaborating on this: if the Curry Howard correspondence is to be interpreted as establishing a strong relation between proofs and programs, should there not be a strong ...
6
votes
1answer
121 views

Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

A function $f: A^* \to A^*$ is regularity-preserving if, for each regular language $L$ of $A^*$, the language $f^{-1}(L)$ is regular. I think I have a proof, as a consequence of more general results, ...
1
vote
0answers
27 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 ...
1
vote
0answers
52 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
36 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 ...
1
vote
0answers
10 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
25 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
31 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 ...
6
votes
1answer
86 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
47 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
46 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
183 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
67 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 ...
7
votes
0answers
98 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
37 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
635 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
131 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
94 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
39 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
41 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
339 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
30 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, ...
3
votes
1answer
89 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
80 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 ...
0
votes
0answers
42 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)$...
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 ...
0
votes
1answer
65 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
49 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 ...
0
votes
0answers
35 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
83 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
51 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
91 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
189 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
102 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
176 views

anything hinting that EXPTIME $\subseteqq$ PSPACE?

Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$?
2
votes
1answer
106 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