All Questions

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

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

Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA Ryan Williams, A new algorithm for optimal $2$-constraint satisfaction and its ...

Short and sweet: The complexity class of primitive recursive functions (WP) is PR (WP, Zoo). What's the complexity class of higher-order primitive recursion (WP)? The motivating context is simply that ...

Preliminaries We consider directed bipartite graphs of the form $G = (V,V',E)$, in which the nodes are partitioned into $V = \{1,\ldots,n\}$ and $V'=\{1',\ldots,n'\}$, with $|V|=|V'|=n$, and $E\...

Is there a standard formula to calculate the number of composite factors using the number of bits of an integer?

Bin-packing (BP) and maximum-makespan (MM) are dual problems. In both problems, the input can be defined as a set $S$ of positive integers, and the output is a partition of $S$. In BP, there is a ...

I'm very new to this field - technically not in it but want to be. I'm very early in my academic career (sophomore at a community college) but decided that I want to add a math major along with my ...

Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)

I would like to show that the halting problem for some variant of two counter machine (Minsky machine) is undecidable: instead of "if c=0 goto i else goto j", there are "if c>d goto ...

Maximal Satisfying Assignment (Lexicographic Boolean satisfiability / LexMaxSAT), the problem of finding the lexicographically maximum x_1, . . . , x_n ∈ {0, 1}^n that satisfies Boolean formula φ, or ...

I am trying to solve a preemptive multi-core scheduling problem, where the input is the tasks. The number of cores M can be decided after seeing the input tasks. I ...

Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings. I want to know whether a version of this extends to perfect $b$-matchings. Suppose we have a bipartite graph $G =...

Consider an oracle $A$ and the language \begin{equation} P(A) = \{x\in \{0, 1\}^{n}: \text{the number of strings in }~A~\text{of length}~|x|~\text{is odd}\}. \end{equation} I am trying to make sense ...

Some preliminaries first. Consider a purely-relational structure (a.k.a. database) $\mathfrak{A} = (A, R_1^{\mathfrak{A}}, \ldots, R_{|\tau|}^{\mathfrak{A}})$ over some finite signature $\tau = \{ R_1,...

I imagine there are some standard results that bear on this, but I'm having trouble finding a proof or refutation of it. Some prelimary definitions. A Henkin structure $A = (A^\cdot, ⟦\cdot⟧_A)$ for ...

The following result is adapted from Anthony and Bartlett, 1999 (Theorem 4.9). Theorem There exist positive constants $m_0 \le 400$, $c_1 \le 8$, $c_2 \le 41$, $c_3 \ge 1/576$ such that, if $(\Omega,\...

Could anyone suggest reading materials on phase transition in MAXCUT problems other than [1]? Thanks. Ref: Coppersmith, Don, David Gamarnik, Mohammad Taghi Hajiaghayi, and Gregory B. Sorkin. "...

Let $G=(V,E,w)$ be a graph and for edge $e\in E$, there is associated weight $w_e$. The max-k-cut wants to partition V into k subsets $P_1,\cdots,P_k$ and maximize $\sum_{1\leq r<s\leq k}\sum_{i\in ...

For points $P=\{x_1, \ldots, x_n\} \subset {\mathbb F}_{2^m}$ define $$\mathcal{C}(P, t) =\{(f(x_1), \ldots, f(x_n)) \mid \mbox{$f\in {\mathbb F}_{2^m}[X]$ has degree $t$}\}$$ and $\mathcal{C}'(P, t) =...

I'm an undergraduate computer engineering student. I know that I like to become a researcher in my major in the future. I also work as a junior web developer at a small start-up, and I think I really ...

A $q$-clique of a graph is a complete subgraph on $q$ vertices. A $q$-clique edge cover of $G$ is a set of subgraphs of $G$ such that each subgraph is a $q$-clique and each edge of G is contained in ...

Consider a random binary tree with $N$ leaves. Each node (except the root node) has a degree of exactly three (two children and one parent). No further restriction is placed on the structure of the ...

Let $p≥3$ an integer. I am wondering whether or not the following problems are NP-hard or not (and if they are, I am looking for a convincing argument, or even better a detailed proof): Let $V_1,\...

I'm following a university course based on these slides, and I have a question about structural operational semantics. As you can see at page 7 (4-th slide), a structural rule is interpreted logically ...

Is it known how to find a (piecewise) straight-line embedding of a single-crossing graph on the plane with exactly one crossing in polynomial time? We are currently trying to come up with a method for ...

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

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

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

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

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

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