All Questions

Filter by
Sorted by
Tagged with
4
votes
2answers
164 views

What's the categorical semantics of definitional equality?

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

Problem in the paper “Stable Minimum Space Partitioning in Linear Time”

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

An NP-hard Hidden Subgroup Problem

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

Linear auto-encoders and PCA with unequal input-output

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

What is few-shots extrapolation?

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

Interpreatation of if..then in terms of recursive function? [closed]

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

Permutation compositions with $n$-cycles [closed]

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

Does this notion of entropy have a name?

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

“Search and Replace” Edit Distances

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

BPP version of a problem related to #P completeness

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

Could someone explain the algorithm from this paper?

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

An (unusual?) risk bound

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

Concentration bounds for hypergeometric distribution

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

Characterization of sublinear time [closed]

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

Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

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

A variant of “hypergeometric” distribution

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

Where does “Quine's Method” in propositional logic originate?

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

Communication complexity of reconstructing a random bit-string of length $n$

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

Examples of SDP constant approximation algorithms on minimisation problems

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

Minimum cut with size bounds $k\leq |S| \leq |V|-k$

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

Expected node probability after finite random walk

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

Expected number of node visits during random walk

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

Can you embed a Turing Machine into the Pi calculus with just one replication operator?

See title. If it is not universal, then how is the power of the pi calculus with this restriction characterized?
1
vote
0answers
63 views

What is this structure? (monad with a kind of partial inverse comonad)

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

Failing to understand a lemma regarding Robust Low Rank Approximation

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. ...
6
votes
3answers
1k views

How does type theory change how one thinks about programming?

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

Reviewing a paper and found a better solution

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

Solving Feedback vertex set using dynamic programming on nice tree decomposition

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

Coloring intersection graph of squares

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

Would this type of circular reference problem be in P or NP?

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

Applications of GCT to transitive closure bottleneck problem

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

3-partition problem is NP-complete. How about “N-partition problem”?

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

How hard is this special 3-partition problem?

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

Result showing that DTIME[T] is strictly contained in random-access NTIME[T]

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

Fixed points of fixed-point combinator?

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

Simple Reduction from ILP to slightly modified Integer Minimisation Problems?

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

Complexity of (Graph) Ramsey Theorem in Sum-of-Squares Proof System

(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 ...
2
votes
2answers
219 views

How to acknowledge answers of TCS in the paper?

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

Commutative operation benefits

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

Is coRE closed under concatenation?

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

Modifying sets to minimize the distance among each pair of the mean value of sets

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

Parametrization of context-sensitive language in polynomial time

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 ...
10
votes
1answer
208 views

Succinctness of regular expressions with empty word

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

How general cost function for $p = \log n$ is the $k$-center cost function?

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

$\#$P hardness of computing weighted sum of degree $2$ polynomials

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 $\...
2
votes
2answers
145 views

What is the point of the eliminator for the unit type?

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

Bound on Set Cover size between multiple families

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

Low Rank Approximation of a hidden subset

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

$\eta$-reduction not locally confluent on well-typed terms

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

Is BigInteger-based Brainfuck Turing Complete?

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

15 30 50 per page
1
2 3 4 5
229