All Questions

The fermionant is a matrix function from physics, which is indexed by a positive integer $k$: \begin{align} \operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A)...

Is there some natural property that is testable in strongly sublinear time (i.e. $O(n^{1-\epsilon})$ for some $\epsilon > 0$) in bounded-degree graphs but not in general graphs? If not such ...

We decomposed a simple polygon into many small regions. Then we estimated a visibility polygon of a point by a subset of the small regions. Now I need the minimum set of visibility polygons that can ...

Consider a bimatrix game problem with matrix $A$ and $B$. Suppose we have a prediction value $\hat{v}$ for the Nash equilibrium value $v$. However, we do not have the strategy profile behind this ...

Let $A\leq_P B$ mean that the language $A$ is polynomial time reducible to $B$. It is a theorem that $A\leq_P B$ and $B\in \text{P}$ then $A\in \text{P}$. My question is, if $A\leq_P B$ and $B\in \...

My master's degree thesis is about geometric intersection graphs online coloring, unfortunately, I have so much doubt when I read papers on this subject and many of the results were incomprehensible ...

While benchmarking a language prototype, I realized that I had a superlinear implementation of a test program, but wasn't sure if it was quadratic or cubic. I stayed up too late and wrote half a page ...

Assuming a hypothetical scenario that complexity class $PSPACE$ is shown to belong to complexity class $NP^{coNP}$ the Polynomial Hirerchy Collapses to a finite level. If I am correct, above result ...

I was trying to determine whether or not two rectangles rotated around their centers were colliding and randomly thought to try the following algorithm: Rotate both rectangles by the negative rotation ...

I need to describe a logic of counting elements of the domain: in each model, the function outputs the number of elements in the domain of the model. What kind of function(s) shall be in the signature?...

I was trying to solve a common problem the other week and upon checking Stackoverflow there was a solution, but it just seemed like there should be a better way to do it. I thought about it for a ...

In some ways, my question is related to this: Is the matching polytope integral? Matching and Horn-SAT are both polynomial time solvable.. So I wonder if there is a Horn polytope, similar to the ...

Consider a universal $\{0,1\}$-$k$-counter machine where each of the $k$ registers has a value in $\{0,1\}$ (as opposed to any non-negative integer in the usual formulation), and there are states $q_1,...

is there any interesting paradox about entropy?

Consider the following matrix factorization problem: Given an $n\times m$ matrix M, find $n\times r$ and $m\times r$ matrices $U$ and $V$ such that $||UV^T - M||_F^2$ is minimized. I have heard it ...

We define $\text{QSAT}_2$ to be the set of all true statements of the form $$ \exists x_1, x_2, \dots, x_k \forall x_{k+1}, \dots, x_n \ \ \phi(x_1, \dots, x_n), $$ where $\phi$ is a CNF on the ...

What are some open problems in quantum computing or complexity theory where a novice researcher could reasonably hope to make contributions with a few months of steady effort? I know this question has ...

I just listened to XYZ talking about "How Universal Is the Idea of Numbers?", and bashing the concept as an accidental historical artifact. He suggested that totally different computational ...

I have a theoretical problem inspired by a real world problem I have come across. I am writing code for some spreadsheets, and part of the process is error correcting names with typos. One ...

I'm doing some work with cryptographic primitives that act on arithmetic circuits. We found a result from a few years ago that would suffice for our purposes, but it assumes the functions in question ...

Suppose given a complete weighted graph $G=(V,E)$, with positive weight. Are there an algorithm that partition $G$ into two clusters $C_1,C_2$ such that sum of heaviest edges in $C_1,C_2$ minimized? ...

The textbook I am currently studying (Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers ...

We are given a family of context-free grammars $\{ G_1, G_2, G_3, ..., G_n, ...\}$ where each $G_n$ generates strings only of length $n$ and obeys other constraints specified below. We want to study ...

According to Turán's theorem (with $r=n/2$), any graph $G$ with $n$ vertices and at least $n(n-2)/2$ edges must contain a clique of size $n/2+1$. My question is: how hard is it to find this clique?$^*$...

In "Relational Properties of Domains", Pitts gives a coinduction principle for pointed cpos (cppos). In corollary 6.13 (below), he specializes it to cppos constructed as fixed points of cppo-...

The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows: For each 3SAT clause: $x+y+z=1$ Introduce 4 new variables $\{a, b, c, d\}$ and replace original clause with below 3 clauses: $R(...

Can anything be said about how typical are odd-H-minor free graphs? (definition of odd-minor-free is in Section 2.2 of notes, page 20 of slides). For instance, for a random graph with $n$ vertices, $...

I am trying to understand why the integrality gap is a lower bound on the approximation ratio. I have read the threads about the integrality gap and the approximation ratio in this forum, but I would ...

I'm currently studying the theory of compiler design and I bumped into a bit of a hurdle with parsers, basically, I don't fully get what the general consensus is on the types of parsers there is, a ...

I have a set of version vectors (or vector clocks) and need to implement a filter function that takes this set and returns a new set where all elements are either "equal", "happened ...

Suppose we have a $k\times k$ matrix $A = \sum_{i=1}^{n} a_i a_i^T$ where $n \leq \mathrm{poly}(k)$ and each $a_i\in\{-1,1\}^{k}$. It is easy to prove that the largest eigenvalue of $A$ is at most $\...

Recall the belief propagation "sum-product" algorithm (from wikipedia): $\forall x_v\in Dom(v),\;$ $\mu_{v \to a} (x_v) = \prod_{a^* \in N(v)\setminus\{a\} } \mu_{a^* \to v} (x_v)$ $ \mu_{...

In his book, An Introduction to the Language of Category Theory,Steven Roman provide us with the following diagram: Then, he states: Note that in this example, the object part of F is not injective, ...

Typically in lambda calculus you have an infinite stock of variables. Could we get away with a finite set?

Suppose you have $n$ switches lined up on a wall, labeled left to right from $1$ to $n$. The switches are either on or off. You get a list of $q$ choices that must be made. A choice consist of two ...

I am reading the book "Understanding Machine Learning" by Shai Shalev-Shwartz and Shai Ben-David. The theorem 6.7 has several equivalent statements for a class of functions $H$. The first ...

Suppose I have a matroid $M = (E, \mathcal{I})$. It is a known fact that given any two bases $X_0$ and $X_n$, we can transform $X_0$ into $X_n$ by repeatedly applying the basis exchange axiom. So ...

Sprouts is a paper-and-pencil game invented by the late John Conway (also known for having invented the Game of Life, in addition to his many contributions to a number of fields of math) and Mike ...

The general question is how to encode constraints in reductions to problems that do not have such constraints. More specifically, there is a straightforward reduction from SetCover to VertexCover. But ...

Imagine we have a stream of bank transactions. Each transaction has a target account and some amount of money. I'd like to find top K accounts over some period of time (e.g. last 7 days) which ...

I am coming from a pure mathematics (in analysis) background and am curious to learn some information and coding theory. I am after some recommendations on texts. Due to my personal background I am ...

In Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide, An oracle builder’s toolkit, Inf. Comput. 182, No. 2, 95-136 (2003). ZBL1025.68041, the authors go through a variety of generic oracles. ...

Sorry for this large and vague question. I am a new grad probability student recently interested in random graph theory(RG). I heard from someone in math department that RG has close relationship to ...

Without loss of generality, I'll only talk about video, but this should apply to any sort of signal. A perceptual hash function (WP) maps videos to fingerprints such that each fingerprint's preimage ...

My question concerns the property of being constant for computable functions ${\mathbb N}\to \{0,1\}$, within any common framework $T$ strong enough to include Heyting arithmetic (and of course not ...

Let us consider $n$ quits $b_i$. Let us start from the state $|0,0,...,0>$ and apply a circuit $C$ composed by $m$ quantum gates, with $m$ polynomial in $n$. The final state is $C|0,0,...,0>$. ...

For a random 3-CNF formula with n variables and m clauses, assume this formula is unsat, what is the lower bound for proving it to be unsat? Some results posted in Lower bounds for random 3-SAT via ...

I am trying to find an easy to use modular decomposition (MD) calculator, possibly online. It is just to make some tests on (small) comparability graphs to decide if it is worthy to use MD as part of ...

There are many models of computability, all giving the same notion of 'computable function'. To pick a few examples: Turing machines (with variants: one-ended, two-ended, multiple tapes...) RAM ...

In the homotopy type theory book section A.2.5 defines $\Sigma$-types, A.2.6 coproduct types and A.2.9 the natural numbers type. If we already have $\Sigma$-types and the natural numbers type can we ...