# All Questions

29 views

### Complexity question from mathematical music theory

Fix an positive integer $N$. A row means any linear ordering $R=(n_i)_{0\leq i <N}$ of the additive group ${\Bbb Z}/N{\Bbb Z}$. Call $R$ a (generalized) all-interval row if the elements of the ...
25 views

### I need a textbook for machine learning with programming approach

I'm taking an online course of machine learning, and I need a good textbook in machine learning better to be with MATLAB applications.
37 views

### Does this game terminate?

Consider the following card game (known in Italy as "Cavacamicia," which may be translated as "stripshirt"): Two players randomly split in two decks a standard deck of cards. Each player gets one ...
43 views

### Consequences of nondeterminism speeding up deterministic computation

If $\mathsf{NP}$ contains a class of superpolynomial time problems, i.e. for some function $t \in n^{\omega(1)}$, $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$, then if follows from the ...
102 views

### What does consistency mean for “computational theories” corresponding to inductive types?

I am currently reading the book by Luo on computation and reasoning. In the book he contrasts inductive types considered as computational theories with axiomatic theories widespread in "standard" ...
27 views

### Direct reduction from Circuit SAT to NAE-3-SAT

I know how to reduce $Circuit-SAT$ problem to $3-SAT$ and thereafter to reduce $3-SAT$ to $NAE-4-SAT$ and finally $NAE-3-SAT$. What I do is that I rewrite the circuit to comprise only of NAND (which ...
29 views

### Theoretical concepts with maximum practical implication

What made me to ask this question is things I have learned in graph theory. I was reading about centrality and found that betweenness centrality is very important in social networks, Whether there ...
21 views

### Initial population for a genetic algorithm from one individual

I'm trying to use GA solve the quadratic assignment problem (QAP). We're planning on using it to be able to provide good solutions when using branch and bound becomes impossible, and as a requirement, ...
40 views

### Faithful functors vs forgetful functors: exact category-theoretic defs?

In category theory, a functor between two categories $C,D$ is a map $F$ that assigns to each object (resp. morphism) $x$ of $C$ a corresponding object (resp. morphism) $F(x)$ of $D$ by respecting the ...
29 views

### What are some examples where the Catalan numbers show up in algorithms/data structures?

For some variants of RMQ data structures, the number of Cartesian trees (i.e. the Catalan numbers) is a part of the running-time analysis. What are some other examples where the Cataln numbers show up ...
5 views

### Whether no local degeneracy in PLC implies edge-protection?

In a paper on Constrained Delaunay tetrahedralization (Meshing Piecewise linear complexes with Constrained Delaunay tetrahedralizations), in section 3, in proof of theorem 2, author claims that if ...
39 views

### Multidimensional Knapsack W[1]-hard when parameterized by dimension

Under Multidimensional knapsack STRONGLY NP-complete it was discussed that the Multidimensional Knapsack problem is strongly NP-hard. Within this discussion the question whether the problem is ...
30 views

### What is the intuition behind Steiner point insertion rules?

I am reading a paper on Constrained Delaunay tetrahedralization (Meshing Piecewise linear complexes with Constrained Delaunay tetrahedralizations). It mentions rules for inserting steiner points but ...
24 views

### W-types vs Inductive types

Martin-Löf type theory uses W-types to define inductive structures like integers, lists, etc. However, calculus of inductive constructions doesn't use them in the same way, inductive types there seems ...
110 views

### What does it mean for CvRDT replicas to transmit their state “infinitely often”?

In Shapiro et al.'s SSS '11 paper on Conflict-Free Replicated Data Types for eventual consistency of distributed replicated objects, they describe a system model in which replicas transmit their state ...
31 views

### Original topic for a computer science bachelor thesis? [on hold]

Im looking specifically for some topics that nobody pay attention on machine learning/KDD/data mining in order to reaserch and make my thesis on some of these... Could anybody provide me some of this ...
315 views

### Exponential gap on neural network layers

I read it here that there are function families which need $\mathcal{O}(2^n)$ nodes on neural network with at most $d - 1$ layers to represent the function while need only $\mathcal{O}(n)$ if the ...
65 views

### Fixed parameter tractable algorithms for graph isomorphism

What are the future directions in fixed parameter tractability of graphs isomorphism after these two recent papers: Reduction Techniques for Graph Isomorphism in the Context of Width Parameters, ...
35 views

### Complete combinator basis for System F-omega

The S and K combinators form a complete (and Turing complete) basis when untyped. Within the Hindley-Milner type-system, and I believe within system $F$ as well, S and K can encode any well-typed ...
163 views

### Are there non-constructive proofs of existence of “small” Turing machines / NFAs?

After reading a related question, about non-constructive existence proofs of algorithms, I was wondering if there are methods of showing existence of "small" (say, state-wise) computation machines ...
107 views

### Approximating $\textrm{AC}^{0}$ by sparse polynomials

Let $f$ be a Boolean function from $\{0,1\}^{n}$ to $\{0,1\}$. We say that $f$ is randomly approximated with error probability $\epsilon$ by a family of polynomials $P$ if \forall ...
36 views

### Complexity of Determining Linear Separability

Be $X := \{x_1,...,x_N\}$ and $Y := \{y_1,...,y_N\}$ subsets of $\mathbb{R}^d$. What is/are the most efficient existing algorithm/s for determining whether X and Y are linearly separable and what is ...
129 views

### Independent set size of a large girth graphs

For triangle-free (girth $\geq 4$) graph $G$. The following theorem holds true Theorem (Ajtai et al.): For a triangle-free graph $G$ with maximum degree $\Delta$, \alpha(G) \geq ...
245 views

### Homotopy type theory and Gödel's incompleteness theorems

Kurt Gödel's incompleteness theorems establish the "inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic". Homotopy Type Theory provides an alternative ...
36 views

### What would be a theoretical time complexity for sorting where you can only swap/compare neighboring elements? [on hold]

Can you point me to a link on an academic paper regarding this? Thank you.
115 views

### Reversible Turing tarpits?

This question is about whether there are there any known reversible Turing tarpits, where "reversible" means in the sense of Axelsen and Glück, and "tarpit" is a much more informal concept (and might ...
39 views

### Totally ordered multicast with Lamport timestamps

I'm studying Distributed Systems and synchronization and I didn't catch this solution of totally ordered multicast with Lamport timestamps. I read that it doesn't need ack to deliver a message to the ...
47 views

### density of undeciability

Consider a function $f:\mathbb{N} \to \{0,1\}$ whose is defined in terms of some universal Turing machine $U$. If $U$ halts when given $x$ as input then $f(x)=1$, otherwise $f(x)=0$. Clearly the ...