6
votes
0answers
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 ...
-5
votes
0answers
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.
6
votes
0answers
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 ...
2
votes
0answers
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 ...
4
votes
1answer
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" ...
0
votes
0answers
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 ...
-2
votes
0answers
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 ...
0
votes
1answer
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, ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
3
votes
0answers
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 ...
0
votes
0answers
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 ...
4
votes
0answers
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 ...
2
votes
2answers
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 ...
-4
votes
0answers
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 ...
6
votes
3answers
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 ...
1
vote
0answers
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, ...
1
vote
0answers
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 ...
8
votes
1answer
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 ...
8
votes
0answers
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 \begin{equation} \forall ...
1
vote
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
-4
votes
0answers
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.
2
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
6
votes
0answers
144 views

Complexity of sum of max subset products

Suppose we are given a sequence $x = (x_1, x_2, \cdots, x_n)$ of $n$ rational numbers, where $x_i \ge 1$ for all $i$. Recall that $[n]=\{1,2,\cdots,n\}$. For each subset $I \subseteq [n]$, let $G(x, ...
3
votes
0answers
39 views

Social choice theory, preference aggregation data sets

I do computational research on preference aggregation. I am quite interested in Kemeny Optimal Aggregation. However I do not find much useful data for preference aggregation in context of social ...
2
votes
1answer
77 views

Set cover with budget on sets

I am wondering if this is a studied variant of the Set Cover problem. We are given a universe $X$, a collection of sets $S = \{S_1, ..., S_m\}$ and integers $c_i$. We want to cover all elements in ...
6
votes
1answer
130 views

NP-hardness proof: looking for some good restricted np-hard problems

To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can ...
2
votes
1answer
39 views

Language with extensible type system?

Is there a practical programming language that has an extensible type system? Or alternatively, an add-on type system that can be used with existing languages? With extensible I mean that the typing ...
3
votes
0answers
111 views

#EXP-Complete problems

Let #EXP be the counting variant of NEXP, in the same way that #P is the counting variant of NP. Are there any known #EXP-complete problems? In particular, has #Succinct Sat (the natural candidate) ...
-1
votes
0answers
10 views

Why use languages in Complexity theory [migrated]

I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model. I have a pretty basic question, but ...
0
votes
0answers
109 views

Equational Logic and First Order Predicate Logic

I am interested in using Equational Theories (ET) together with Equational Logic (EL) found in algebraic specification languages such as CafeOBJ . I wish to use ET+EL to represent and prove ...
10
votes
0answers
87 views

Sylver Coinage Game

A game in which the players alternately name positive integers that are not sums of previously named integers (with repetitions being allowed). The person who names 1 (so ending the game) is the ...
2
votes
0answers
31 views

BSP, but with curved surfaces (NURBS? kernelized support vectors?)

Let's say that I wanted to use a BSP not just for partitioning points, but also to define surfaces, i.e. that I have $\mathbb{R}^2$ and I want to be able to continuously map at least some easily ...
0
votes
0answers
34 views

Questions about threads and locking [on hold]

I am currently reading Fuss, Futexes and Furwocks: Fast Userland Locking in Linux and came across this quote: In a fair locking scheme the lock is granted in the order it was requested. This can ...
9
votes
1answer
216 views

How to write the introduction of a research paper?

Apologies if this is too broad a question for this forum, but I'm interested in specific tactics and tips that researchers (in TCS) use to write the introduction of a research paper.
1
vote
0answers
66 views

Restoring symmetry in certain combinatorial bijections?

I'm interested in two 'natural bijections' that involve labeled forests and Young tableaux. Let me give the definition for labeled forests. By this, we mean a pair $\cal{F} = (F,f)$ where $F$ is an ...
-1
votes
0answers
57 views

Exams about post-graduate in computer science [on hold]

This is just a curious question.. Someone knows where can I download exams of years ago about post-graduate on computer science? Maybe exams from Oxford, MIT, Stanford, University of Tokyo.. whatever. ...
0
votes
0answers
52 views

A self-contained proof that OrdHorn relations are tractable?

I'm currently investigating a family of temporal relations called 'Ordered Horn' ($OH$ for short). This class was introduced in 'Reasoning about Temporal Relations: A Maximal Tractable Subclass of ...
2
votes
0answers
105 views

Fixed-parameter tractability of SCS: finding the missing proof(s)

I am interested in two "super-objects" problems from computational biology. The first problem, dubbed Shortest Common Supersequence ($SCSy$), takes a family of sequences $s_1,\ldots,s_k$, and seeks a ...
3
votes
1answer
196 views

What is logic programming and does it really add anything new to the logic?

I am acquinted with the basics of such notions as logic programming, monotonic and non-monotonic reasoning, modal logic (especially dynamic logic) and now I am wondering - does logic programming ...
-2
votes
0answers
147 views

Is this notion of 'regular graph' known?

Let $S$ be a set, and consider a weighted digraph $D = (S,A,W)$ ($A$ a symmetric set and $W : A \rightarrow \mathbb{R}$ a weight function). Let $d$ be a positive real. By a $d$-potential for $D$, we ...
11
votes
1answer
154 views

Testing isomorphism of asymmetric graphs

While reading the question Examples where the uniqueness of the solution makes it easier to find, a new (easier?) question came to my mind: actually we don't know if the Graph Isomorphism ($GI$) ...
25
votes
1answer
398 views

Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...
1
vote
0answers
63 views

Relations between Arboreal Group Theory and Tree Group Actions? [migrated]

By a tree group action, we mean an action of a group $G$ over the infinite regular binary tree $T_2$ such that for each $g \in G$, the mapping $x \rightarrow g.x$ is an automorphism of $T_2$; these ...
2
votes
0answers
50 views

The Alexander-Conway polynomial: from knots to braids? [migrated]

The Alexander-Conway polynomial was the first knot invariant to be discovered, as far back as 1923 according to this link. Given that knots can be expressed in terms of quasi-toric braid closures, it ...

15 30 50 per page