Reference-request is used when the author needs to know about work related to the question.

learn more… | top users | synonyms

9
votes
3answers
300 views

Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?

Denote by $\delta^+(G)$ the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree. In a related question, I've mentioned the Ghouila-Houri extension of Dirac's theorem on Hamiltonian ...
0
votes
0answers
122 views

An interesting class of colored graphs?

Let $G$ be a complete graph edge-colored with $k$ colors. We say that $G$ is Gallai-colored if no triangle is colored with three distinct colors. Fix a tuple of integers $c = (c_1,\ldots,c_k)$. We may ...
3
votes
0answers
104 views

Generating quadratic optimization problems amenable to quantum annealing

Some context: there is a current debate in adiabatic quantum computing over whether a particular machine, the D-Wave quantum annealer, can outperform a classical algorithm [*]. Earlier this year, a ...
7
votes
3answers
369 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 ...
7
votes
1answer
168 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 ...
3
votes
0answers
130 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) ...
2
votes
0answers
128 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 ...
12
votes
1answer
186 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$) ...
3
votes
2answers
129 views

TCS oriented refs/survey on group theoretic word problem

The word problem for groups was shown to be Turing-complete in 1955 but has many decidable subcases. This problem arose more in mathematical group theory than in theoretical computer science, but now ...
2
votes
1answer
69 views

Paper about the upper bound of the number of inequalities to describe the Integer hull of a polyhedron

I am interested in the upper bound of the number of inequalities to describe the integer hull of a polyhedron. That is, given an integer programming problem with n inequalities which construct a ...
4
votes
1answer
100 views

parameterized algorithms for geometric set cover

Are there any parametrized algorithms $W$-hardness results known for the computational problem Geometric Set Cover? It is known that set cover problem is $W[2]$ hard when parametrized by the solution ...
5
votes
2answers
113 views

Learnability of constraint satisfaction problems CSPs?

This may sound more like a soft question but I am struggling to find an answer for it. While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of ...
4
votes
1answer
88 views

Dual Barnette's Conjecture

Is every Eulerian triangulated (planar) graph Hamiltonian? On the other hand we have that: Barnette's Conjecture (Open): Every cubic bipartite (3-connected) planar graph is Hamiltonian. ...
25
votes
2answers
659 views

Kolmogorov's conjecture that $P$ has linear-size circuits

In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find ...
7
votes
1answer
168 views

Tight examples for approximating the feedback vertex set problem

There are several 2-approximation algorithms for the UNWEIGHTED feedback vertex set problem (FVS), which are summarized in [4]. Note that the reduction from vertex cover to FVS is ...
-1
votes
1answer
107 views

is determining an unknown CFL from intersection of two CFLs decidable?

this problem was asked over a week ago on cs.se now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it ...
2
votes
0answers
74 views

Assessing the unavoidability of a set kof structures?

Consider a family of structures equipped with a "sub-structure" relation - e.g. subwords, subpermutations or induced subgraphs. Given a set of structures $\cal{K}$, we denote by $Av(\cal{K})$ the ...
4
votes
0answers
57 views

Complexity of equivalence testing of arithmetic circuits

I have a very specific problem that appears to be close to equivalence testing for arithmetic circuits (checking whether the computed functions are the same). Since I'm completely new to the field, ...
2
votes
5answers
422 views

Problems that are hard to prove in $\mathcal{P}$

What is the famous "hard" problems that were shown to be in $\mathcal{P}$ after? I want to know a list of problems that are difficult to prove in the class of "easy" problems? Maybe like matching, ...
2
votes
0answers
73 views

Existence of bijective proofs involving Yamanouchi words?

The following notion comes from algebraic combinatorics and might have some connections to language/permutation theory. Fix an integer $k$. Let us call a $k$-Yamanouchi word a sequence $u$ of integers ...
14
votes
2answers
187 views

On the status of learnability inside $\mathsf{TC}^0$

I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside ...
5
votes
1answer
98 views

Probability of random (in)finite graphs being isomorphic

I once skimmed a paper which examined the probability of two (infinite) graphs picked at random being isomorph. The surprising result was that for two random infinite graphs this probability is quite ...
2
votes
0answers
61 views

A number-theoretic bijection in modular arithmetic

Fix an integer $n$. Considered as a multiplicative group, the sets $A = (\mathbb{Z} / n \mathbb{Z})^*$ and $B = \mathbb{Z} / \phi(n) \mathbb{Z}$ have the same cardinality $\phi(n)$, but it does not ...
6
votes
3answers
297 views

Multidimensional knapsack STRONGLY NP-complete

Who can point me to a reference where it is actually shown that multidimensional knapsack is strongly NP-complete? I have found loads of papers where they claim it is, without citation; I have found ...
4
votes
1answer
317 views

How can I prove formally semantic equivalence of programming languages?

I would like to compare two languages which are from different programming paradigms. Both langauges are object oriented languages, but one of them a multiparadigm language because it supports ...
3
votes
1answer
137 views

$NP$ set as a function of combinatorial space

Inspired by this answer given by Noam, which I think implies (if I understood correctly his answer ) that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from a ...
1
vote
4answers
182 views

Turing-complete computation models on graphs

There are many Turing complete computation models and new ones are devised all the time. I am looking for Turing-complete computation models based on graphs?
2
votes
1answer
133 views

A curious Wilf equivalence class of function compositions

I was enumerating pairs of functions from a size $n$ set into itself, and ran into these three relations which all generate the same integer sequence starting at index zero: 1, 1, 6, 87, 2200, 84245. ...
1
vote
0answers
78 views

Chromatic number of a graph where neighbourhood of each vertex is isomorphic

Consider a graph $G(V,E)$. For any two vertices $v_1 , v_2 \in V$, the subgraph induced by the neigbourhood of vertex $v_1$, denoted by $G_{v_1}$ be isomorphic to the subgraph induced by the ...
6
votes
0answers
62 views

Fast convergence of a contagion process in special graphs

The process: Given is a clique $C_n$ of size $n$. Consider the following synchronous process, also known as the (synchronous) voter model (e.g., Even-Dar and Shapira): Define an indicator variable ...
11
votes
1answer
271 views

APX Hardness implies no QPTAS?

So, a quick search on the web led me to believe that "APXHardness implies that no QPTAS exist for a problem unless [some complexity class] is included in some [other complexity class]" and it is well ...
1
vote
0answers
62 views

Good references for understanding the underlying abstractions/ideas of functional programming?

What are some good references, not very dense, to understand the underlying math and computability aspects of the notion of "functional programming"? I'd like to have something that talks about it ...
6
votes
1answer
174 views

Max-weight connected subgraph problem in planar graphs

The maximum-weight connected subgraph problem is as follows: Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$. Output: a maximum-weight subset $S$ of ...
16
votes
2answers
363 views

A good reference for complexity class operators?

I'm interested if there exist any good expository articles or surveys to which I can refer when I write about complexity class operators: operators which transform complexity classes by doing things ...
12
votes
2answers
179 views

Reference for Dyck languages being $\mathsf{TC}_0$-complete

Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar $$ S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon $$ over the set of symbols ...
18
votes
2answers
415 views

Problems with efficient solution except for a small fraction of inputs

The halting problem for Turing machines is perhaps the canonical undecidable set. Nevertheless, we prove that there is an algorithm deciding almost all instances of it. The halting problem is ...
6
votes
1answer
151 views

Natural Transformations and Parametricity

In Theorems for Free!, Wadler says that the characterization of parametricity can be re-expressed in terms of lax natural transformations and this will be the subject of a further paper. Which paper ...
3
votes
1answer
70 views

Is Square DH hard in Bilinear Groups?

Let $G$ be a group, $g ∈_R G, x ∈_R Z_q$, and $e: G \times G \rightarrow G_T$ be a bilinear paring. Then, given $g, g^x$, is it still hard to compute $g^{x^2}$? 1. In other words is Square ...
0
votes
2answers
88 views

Packing problems with repetitions

In packing problems, we need to select a set of sets of items, such that no item is chosen twice (in $Set-Packing$, the actual items must not be packed twice, in $Graph-Packing$ the copies of the ...
7
votes
2answers
135 views

A tool for minimal NFA computation

It is well known that minimizing an NFA for a fixed regular language is $PSPACE-Complete$. As far as I know, there are no better than trivial algorithms for minimizing such NFA, but there's a little ...
4
votes
0answers
93 views

Low space computation and branching program

One of the most elemental result of relationship between boolean circuit size and polynomial uniform computation is Pippenger and Fishers simulation: $DTIME[T(n)]\subseteq SIZE[T(n)\log T(n)]$. I ...
9
votes
1answer
329 views

Best sources for communication complexity

What are some of the best sources (books and papers) to motivate and learn communication complexity on its own and in connection with its relation to computational complexity theory?
1
vote
1answer
86 views

Covering by disjoint sets

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. I'm interested in the approximability of two problems, or in ...
0
votes
0answers
90 views

Turing reduction from integer factorization to clique

Is there a general web repository of reductions between and among various NP problems? In particular, I'm looking for a direct Turing reduction from integer factorization (candidate for ...
2
votes
4answers
300 views

Research in Coding Theory

I have just started learning about coding theory. Hence, I would like to ask for your suggestions and guidance for a very beginner like me. Which books are good for beginning coding theory? (I start ...
9
votes
1answer
114 views

Complexity of counting the number of edge covers of a graph

An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: ...
10
votes
2answers
291 views

Why is linearizability a safety property and why are safety properties closed sets?

In Chapter 13 "Atomic Objects" of the book "Distributed Algorithms" by Nancy Lynch, linearizability (also known as atomicity) is proved to be a safety property. That is to say, its corresponding trace ...
1
vote
1answer
150 views

Is there an analogy of a vertex separator for hypergraphs?

Numerous parameters are defined and considered in the graph theory. I am interested in analogy of these parameters in theory of hypergraphs. Is there some survey or book or lecture notes about ...
12
votes
3answers
508 views

Graph coloring minimizing the number of colors in every independent set

Is the following claim known? Claim: For any graph $G$ with $n$ vertices there exists a coloring of $G$ such that every independent set is colored by at most $O(\sqrt{n})$ colors.
5
votes
0answers
148 views

Complexity of the Transductive SVM training problem

The Transductive Support Vector Machine training problem is a non-convex mixed integer programming problem: Transductive Support Vector Machine training problem. $$ \begin{align} ...