All Questions

The categorical semantics of a dependent type theory is normally described as a CwA/CwF/CompCat/etc. and in these models, we can talk about propositional equality by interpreting an 'identity type'. ...

The paper Stable Minimum Space Partitioning in Linear Time describes an algorithm that stably sorts a binary array (an array whose elements can only have two distinct values) in $O(n)$ time complexity ...

I've encountered a model which can be thought of as a version of the Hidden Subgroup Problem (https://en.wikipedia.org/wiki/Hidden_subgroup_problem), but that doesn't quite meet the standard problem's ...

It is a well-known fact that linear auto-encoders are equivalent to PCA, i.e. for the data matrx $X\in {\mathbb R}^{n\times N}$ the task $$ \min_{W\in {\mathbb R}^{n\times k}}||X-WW^TX|| $$ has a ...

I'm reading the paper "Learning how to ask" by Qin & Eisner and in the abstract, they mention that using prompts, language models can perform tasks other than text generation. Examples ...

I am trying to understand various commands in high level programming in terms of turing machines (i.e. computable functions). For eg for/while loops can be though as recursion of a specific function. ...

Not sure if this is suitable for cstheory or math, so posting in both places. Consider the set $\Pi$ of permutations $\pi: [n] \to [n]$ where each such $\pi$ is an $n$-cycle (i.e., one big cycle ...

Recently I stumbled upon the following notion of entropy which seems quite natural to me. I am looking for its "real" name and/or any references where it might come up. I tried searching ...

Which results are known about the string edit distances using the edition operator "Search and Replace"? Edit distances were traditionally used in bio informatics and to correct ...

Given a $CIRCUITSAT$ instance $\varphi(n)$ in $n$ variables and a fixed $k>1$ the problem of deciding if the number of satisfying witnesses is $2^n\big(1-\frac1k\big)$ or $\frac{2^n}k$ is $PP$ ...

Trying to get a fair understanding of our artificial immune systems. To do this I’ve been reviewing this paper, but the algorithm and mathematics is over my head, could someone explain the below to me ...

I am told that that a bound on the generalization error of the following form exists in terms of something called the ``shattering coefficient" - but I am not able to reference this quantity in ...

I asked a similar question a while back. I have reformulated the question. My original intention was to ask this question. Suppose we have an urn containing $N$ balls, $M$ of which are red, rest are ...

Let $TIME(f(n)) = $ the collection of languages decidable by a one tape DTM in $O(f(n))$. I am looking for a characterization of this class of languages, if $f$ is sublinear. This means there is not ...

Often, we can model combinatorial optimization problems with an Integer Program. Then there is an associated Linear Relaxation which drops the integrality constraints on the variables. Let's say we ...

This is already posted here. We all are aware of Hypergeometric distribution. Let me first briefly discuss what it is. Suppose we have an urn containing $N$ balls, $M$ of which are red, rest are blue. ...

Hein (407-408) states that Quine's method "...uses these (14) properties together with basic equivalences to determine whether a wff is a tautology, a contradiction, or a contingency." The ...

This seems like a folklore claim but I cannot find any reference to it. If Alice has a bit-string of length $n$ where each entry is independently set to 0 or 1 equiprobably, and Bob's goal is to ...

I was recently going through a survey on semidefinite programming and its use in approximation algorithms. Here are some problems I am familiar with that have SDP approximations: Max Cut ($\approx 0....

It is known by the max flow min cut theorem that the minimum cut problem is in $P$. I am interested in knowing what is known on the complexity of the minimum cut with size $k\leq |S| \leq , |V|- k$. ...

Let $G=(V,E)$ be a connected, non-bipartite graph with $n$ nodes and $m$ edges. Consider a random walk of length $t$ on $G$ that starts at a uniform random node. The sequence of nodes in the random ...

Say we have a graph $G = (V,E)$ and all we know about the graph is the degree $deg(n)$ of each node $n$, $|V|$, and $|E|$. Say we begin a random walk of length $l$ starting at a random node. What is ...

See title. If it is not universal, then how is the power of the pi calculus with this restriction characterized?

I have encountered a structure that looks like a monad with a one-sided inverse and some additional properties. I am not sure which properties of this structure are essential and which are accidental, ...

I am reading Low Rank Approximation in the Presence of Outliers by Bhaskara and Kumar and kind of stuck at the proof of Lemma 9. The paper studies robust (to outliers) low rank approximation problem. ...

I have been dabbling in HoTT and I am convinced that dependent type theory is much more suitable than set theory for proof assistants. Now, this made me wonder - how fundamental is Type Theory ...

I was reviewing a paper of a double-blind conference (ML/AI-based conference). The authors improved the approximation bounds for some special instances of a problem. To understand their proof better, ...

I am interested in a specific solution to the Feedback Vertex Set In theorem 7.10 from this book, it is stated that Feedback Vertex Set can be solved in $k^{O(k)}$ using tree decomposition. I learned ...

It is known that the coloring intersection graph of axis-parallel rectangles is NP-Hard. What about squares and more specific case "unit squares"? Thanks.

The system of equations below is a circular reference problem. $$\vec{a}_m(n)={\Large{\sum_{m=1}^t}}\sum_{n=1}^sf\left(\vec{x}_m(n),\vec{v}_m(n)\right)$$ $$\vec{v}_m(n+1)=h\left(\vec{a}_m(n),\vec{v}_m(...

GCT so far has not provided any non-trivial bounds for matrix multiplication or permanent. The transitive bottleneck problem is related and is concerned about matrix powering and iterated matrix ...

It is well known that 3-partition problem is strongly NP-complete. (https://en.wikipedia.org/wiki/3-partition_problem) Then, My question is, how about "N-partition problem"? Is it NP-...

The definition of the original 3-partition problem is that: given a set $A$ of elements $A=\{a_1,a_2,...,a_{3m}\}$ and a positive integer $B$, and a positive size $s(a_i)$ for each $a_i \in A$ where $...

I recall seeing a result showing that multi-tape DTIME[T] is strictly contained in random-access NTIME[T] for reasonably large T (so not the PPST proof with the $\log^\star$ sort of factors), but I ...

A fixed point f of a fixed-point combinator would be a function that has itself as a fixed point: f(f) = f. The only such ...

I was introduced to the spectral bisection problem through numerical analysis today, and that it can be reduced to almost what seems like an ILP with some constraints that can be expressed the same ...

(One formulation of) Ramsey's theorem states that any colouring of edges of the complete graph with $4^n$ vertices with two colours will contain a monochromatic clique of size $n$. I am new to proof ...

I am researcher in a company from last 5 years. I have received few answers on Theoretical Computer Science stack exchange regarding my current research work. They are not the main part of the paper ...

With an associative operation I can rewrite a computation tree + / \ + 4 / \ + 3 / \ + 2 / \ 0 1 to be more efficient ...

I know that RE is closed under union, intersection, and concatenation (but not complement). It is likewise easy to show that coRE is closed under union and intersection (but not complement). What ...

Given $n$ points, each point $x_i$ has a value $v_i \in \mathbb{R}^{d}$, and there are $m$ point sets $\{S_1,\dots, S_m\}$ that each point set consists of some points. The size of point sets can be ...

Let $\Sigma$ be a finite alphabet. Let $L\subset \Sigma^*$ be a context-sensitive language containing a word of every length. Can we always find $f:\Sigma^*\to L$ computable in polynomial time in ...

Consider regular expressions on some alphabet $\Sigma$, without the empty word: $$e,f:=a\in\Sigma\mid e\cdot f \mid e+f\mid e^+$$ These $\varepsilon$⁻free expressions can define all regular languages ...

The $k$-clustering problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the ...

Consider polynomials $f: \{0, 1\}^{n} \rightarrow \{0, 1\}$ over $\mathbb{F}_2$ (addition and multiplication are taken modulo $2$.) Consider integers $x \in \{0,1\}^{n}$, written in binary. Let $\...

In the HoTT book p. 436 A.2.8 the eliminator $\mathrm{ind}_{\mathbf{1}}$ for the unit type is described. What is the point of it? What if you did not introduce it and instead just replaced all the ...

I am working on a related Steiner tree problem that I have reduced to Minimum Set Cover, but stumbled across this related problem and got stuck. Given an universe of $n$ elements $U = \{1,2,\ldots,n\}$...

Let $P$ be a set of $n$ points in $\mathbb{R}^d$ and $Q\subseteq P$ with $\vert Q\vert \geq \alpha n$ for some constant $\alpha\in(0,1]$. Given a $j$-dimensional affine subspace(flat) $F$ consider the ...

This paper says: "In the presence of a unit type, $\eta$-reduction is not even locally confluent on well-typed terms [20]." [20] is a reference to a 300-page book with no further details and ...

All of the proofs of Turing-Completeness I've found for Brainfuck rely on its cells being fixed-width integers that wrap around upon over/underflow. The "parent language" P'' on which ...