All Questions

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

How does complexity of a counting problem influence wether it admits a closed form formula or not?

In https://arxiv.org/abs/1412.1505, the section "Results on Data Complexity" mentions the fact that since the authors are about to proove $\#P_1$ complexity for weighted model counting in ...
2
votes
0answers
43 views

Fine-grained hardness results on exact computation of matrix multiplication output size

Consider two boolean matrices of dimension $\sqrt{N} \times \sqrt{N}$ with total $O(N)$ non-zero entries. Let $|OUT|$ denote the number of non-zero entries in the product of the two matrices. Is it ...
0
votes
0answers
23 views

Remove cycles from a stochastic comparison matrix, while doing the least amount of editing

Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison ...
0
votes
0answers
12 views

Examples of random deployment in wireless sensors networks

I have been doing some research and have found a lot of papers on the subject of random deployment in wireless sensor networks, but I haven't found a single example of its usage. Has it been used ...
2
votes
1answer
85 views

What graphs on $\mathbb{N}$ can be encoded as regular languages?

Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers ...
0
votes
0answers
43 views

Unambiguous Problems and Classes over Reals

Are there unambiguous analogues of $NP_{R}$ (using the BSS model, in all discussion)complete problems, and any results known about them? For instance, the canonical $NP_{R}$ complete problem $4FEAS$ (...
1
vote
0answers
19 views

Decidability of regular partition construction given its existence

Let $G = (N,T,P,S)$ be a context-free grammar where $T,N$ are sets of terminals and nonterminals respectively, $P$ contains all the productions of the grammar, and $S \in N$. If we know that $G$ is LL(...
1
vote
0answers
60 views

Functional abbreviation for Inst expression in Turing's 1936 paper

In Turing's 1936 paper "On Computable Numbers", For a Turing Machine $M$, $Inst(q_i S_j S_k L q_l ) $ means that if $M$ scans symbol $S_j $ under $m-configuration$: $q_i$, then symbol on ...
-2
votes
1answer
81 views
+50

How to calculate complexity in a high dimensional space?

Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong. For a specific f(), I'm defining a term '...
-5
votes
0answers
14 views

Prove Polynomial Runtime of a 3-coloring Optimization Problem

Suppose we are given a graph $G$, and we want to color each node with one of three colors, even if we aren’t necessarily able to give different colors to every pair of adjacent nodes. Rather, we say ...
1
vote
0answers
24 views

Nominal Tree Languages i.e. with Binders and Infinite Symbols?

I'm wondering if there has been any research done into automata that accept languages of trees that can bind arbitrary variables, and are considered equal under alpha equivalence. I've found so far: ...
4
votes
1answer
78 views

Box stacking problem, and variants

You are given $n$ boxes and want to stack them to make a tallest possible tower, but you can only stack a box on top of another if the base is smaller in both dimensions. This is a classic dynamic ...
2
votes
1answer
198 views

Can the halting problem be solved probabilistically?

Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random ...
-2
votes
0answers
15 views

How to set the proper threshold to remove the features in feature selection? [closed]

With a classification problem with 256 features, I will apply feature selection to find the proper attribute will provide the highest accuracy. How can I set the criteria or threshold for selection of ...
0
votes
0answers
21 views

A continuum version of the 1D k-means clustering problem: constant factor approximations

Modify the k-means clustering problem in 1D by assuming that, instead of a finite number of observations, we must classify into $K$ clusters a continuum of observations, distributed on the unit ...
5
votes
1answer
153 views

Is there an equivalent to VC-dimension for density estimation as opposed to classification?

VC-dimension can be used to quantify the capacity for classifier models and compute generalization bounds, but is there an equivalent concept that can be applied to density estimation, e.g. to compute ...
0
votes
0answers
56 views

Is there any second-order logic finite satisfiability checker?

I know that there are implementations of first-order (finite) satisfiability checking that, given a finite set of axioms, searches for a finite model that satisfies them all. I would like to ask ...
1
vote
0answers
29 views

Three Clique Sums of Bounded Treewidth and Bounded Genus graphs

This question asks about the forbidden minors of the class of graphs that can be formed by taking three clique sums of planar graphs and bounded treewidth graphs(The class is defined for some constant ...
2
votes
1answer
54 views

Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?

The kernel of a parameterized problem $L$ is a reduction $(x,k) \mapsto (x',k')$ such that: $(x,k) \in L \Leftrightarrow (x',k') \in L$ $|x'| \leq f(k)$ for some function $f$ $k' \leq g(k)$ for some ...
0
votes
0answers
75 views
+50

reordering a DAG with the minimum changes

Consider a DAG $(V,A)$ with an initial permutation $(v_1,v_2,…,v_n)$. We want to arrange the $n$ vertice in topological order while keeping as many vertices as possible. The problem is: Is it NP-hard ...
0
votes
1answer
44 views

Is every countable, finite-branching LTS bisimilar to a tree?

Let $L$ be a finite set of labels, and let $\mathcal{C}$ be the set of finitely-branching transition systems labeled by $L$ and with a countable set of states. Let $\sim$ denote the bisimulation ...
1
vote
1answer
28 views

Best approximations of Minimum Dominating Sets in chordal graphs

I am searching results and papers related to the (in)approximability of the Minimum Dominating Set problem in chordal graphs. In particular, what is the best approximation ratio achievable in polytime ...
1
vote
0answers
13 views

Power of Hyperedge Replacement Grammars (HRGs)

Can HRGs generate languages which equal or include the following graph languages: All (bipartite) graphs of bounded degree All (bipartite) planar graphs of bounded degree All (bipartite) planar ...
0
votes
1answer
88 views

VC dimension for balanced binary decision trees

What is the VC dimension of all balanced binary decision tree of depth $k$ in $\{0,1\}^d$? Does it depend on depth $k$ or dimension $d$?
1
vote
1answer
74 views

Phonology and lambda calculus

I wonder whether there is any relationship between lambda calculus and phonology (study of phonemes). Specifically, how one would use the concepts of lambda calculus (typed or untyped) in the study of ...
1
vote
1answer
111 views

Which are the best universities for a DPhil/PhD in proof theory and automated reasoning?

I'm an undergraduate student studying computer science and I'm interested in doing a PhD after I graduate. I would like to do research in proof theory and automated reasoning, specifically in ...
7
votes
1answer
150 views

On the usage of Arora and Barak's main lemma in their proof of the PCP theorem

I am a mathematician working toward understanding a proof the the PCP theorem using Arora and Barak's textbook Computational Complexity. I believe I found a few (fixable) errors in Section 22.2, in ...
0
votes
0answers
64 views

Efficient sampling of primes

Using rejection sampling, it is trivial to construct a Las Vegas algorithm for sampling a uniformly random prime number less than a given $N$. What is known about sampling algorithms that run in worst-...
0
votes
1answer
62 views

Time complexity of finding chain decomposition of partially ordered set

Given a partially ordered set $P$ with $n=|P|$ and width $w$: -What is the best known complexity (in expectation) for finding a chain decomposition of $w$ chains? -What is the best known complexity (...
-2
votes
0answers
32 views

Arithmetic complexity of exponentiation

I wanna find out whether following pseudocode has an arithmetic complexity of $\mathcal{O}(n^2)$ or $\mathcal{O}(n)$... ...
2
votes
1answer
60 views

A conjecture on 4-coloring maximal planar graphs

The question/task is to prove/disprove the conjecture below. Let $G$ be a maximal planar graph with a 4-coloring $f$. Let $(a,b,c,d)$ be a cycle in $G$. Let $S$ be the collection of all $a,c$-paths in ...
-3
votes
0answers
49 views

Can we do non-binary maths in computing? [closed]

forgive my lack of basic computer knowledge but, why do we have to use binary representations of numbers in mathematics in computing? I mean it seems like I am being cheated by non-whole number digits ...
3
votes
0answers
53 views

Deciding whether an arbitrary context-free grammar generates a deterministic push-down automata?

I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the ...
-1
votes
0answers
29 views

Distinguishing integer functions of similar encoding complexity

Let $f(n) : \mathbb{N} \to \mathbb{N}$ be an integer function and $C(f)$ the minimum number of "symbols" needed to "encode" $f$ in a suitable representation. This representation ...
2
votes
1answer
131 views

Is modal $\mu$-calculus “equivalent” to bisimulation?

I know that propositional modal $\mu$-calculus $L\mu$ is bisimulation-invariant. However, I'm curious to what degree it captures bisimulation. Q1: Given two labeled transition systems $T_1$, $T_2$ ...
4
votes
0answers
39 views

Applications of solvability in the λ-calculus

What are applications of solvability / unsolvability, and of operational characterizations of solvability? Solvability In the (untyped pure call-by-name) $\lambda$-calculus, a closed term is said to ...
-4
votes
0answers
34 views

Time complexity of counting the non-prime numbers

So i have a code that i need to find (and proof) the time complexity of it: For ( i = 2 -> N ) For ( j = 2-> sqrt(i)) If(i%j==0) K++ Break; Would really appreciate if someone can help.
3
votes
1answer
199 views

Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$

Let $G=(V,E)$ be a graph. Let $m(G)=|E|$ and $n(G)=|V|$. There are two different density definitions for $G$: $$d_1(G)=\frac{m(G)}{n(G)}$$ and $$d_2(G)=\frac{m(G)}{n(G)-1}.$$ Let $H^* \subseteq G$ be ...
8
votes
0answers
59 views

Forbidden Subgraph Characterization for Graphs with few Maximal Cliques

Consider the following property of undirected graphs. A graph has the $s$-vertex overlap property if every vertex is contained in at most $s$ maximal cliques. I am interested in forbidden induced ...
3
votes
1answer
107 views

Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general case, it is exponential. I am trying to determine whether the ...
4
votes
0answers
85 views

A possible error in the semantic chapter of the ISO standard for the Z specification notation

I may have found an error in the ISO standards document for the Z specification notation, namely ISO/IEC 13568:2002, "Information technology — Z formal specification notation — Syntax, type ...
5
votes
1answer
60 views

Upperbound for max degree of k-tree completion

Definitions: For a graph $G$, a $k$-tree completion of $G$ is a $k$-tree obtained by adding edges to $G$ (if $G$ has a $k$-tree completion, $G$ is said to be a partial $k$-tree). The least integer $k$ ...
7
votes
0answers
122 views

Reference for computing the rank of a matrix in polynomial time

In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as ...
1
vote
0answers
76 views

Looking for an online community specializing in the Z specification language, where I can ask questions

Where can I find an online community specializing in the Z specification language, where I can ask specific questions about the ISO standard for Z?
2
votes
0answers
52 views

Minimum feedback arc set for dense directed graph

This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\...
1
vote
1answer
101 views

Face-splitting product of two Vandermonde matrices: When is is invertible?

Let $A$ and $B$ be two $n^2 \times n$ Vandermonde matrices with coefficients $\alpha_1,\ldots,\alpha_{n^2}$ and $\beta_1,\ldots,\beta_{n^2}$. Let $M$ be the face-splitting product of $A$ and $B$, that ...
1
vote
0answers
52 views

Lipschitz composable compressor

Def. We call $C: \mathbb R^d \to \mathbb R^d$ a $\delta$-compressor (or contractor) if for all $x$ $$\|C(x) - x\|^2 \le (1 - \delta) \|x\|^2$$ Intuitively, $C(x)$ is not too far from $x$. Note that $\...
3
votes
0answers
160 views

Are Julia sets (theoretically) Turing-complete?

Could any (computational) function be expressed in terms of a Julia set? Is the space of all possible computational functions (which I think is defined by Turing completeness) translatable to the ...
2
votes
0answers
82 views

Is there a competitive algorithm for this online scheduling problem to minimize the truncated gaps?

Time is discrete. There are $n$ time-slots and a single job that can be scheduled on one machine of budget $B$. If the job is scheduled at time-slot $t$, then it will consume $c(t)$ units of the ...
7
votes
1answer
281 views

How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM?

In $O(n^2)$ steps, a 1-tape TM can simulate a 2-tape TM that runs for $O(n)$ steps. How fast is an equivalent 2-tape TM known to run compared to a $O(n^2)$ time, 1-tape TM? "Open question" ...

15 30 50 per page
1
2 3 4 5
219