Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [reference-request]

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

16
votes
1answer
973 views

“Almost sorting” integers in linear time

I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but ...
6
votes
2answers
231 views

Log space algorithms for modular decomposition tree

Can we have log space algorithms for modular decomposition tree (see definition) for any graph? If not, can we have log space algorithms for modular decomposition tree for any particular graph class? ...
2
votes
0answers
59 views

How to extend Solomonoff Induction to continuous domain

Informally speaking, Solomonoff Induction provides an Bayesian optimal way to predict the next symbol from observed symbol sequences $S_1S_2S_3...S_n$ where each $S_i$ belongs to a finite symbol set $\...
6
votes
0answers
84 views

Using epsilon biased sets for circuit lower bounds

I have seen instances of how the technique of epsilon biased sets can be used to construct hard functions against a circuit class - like how in the recent paper of Kane-Williams this was used to ...
9
votes
1answer
184 views

Was counting complexity first introduced by Valiant in 1979?

Was #P first introduced in [1]? [1] Valiant, Leslie G. "The complexity of computing the permanent." Theoretical computer science 8.2 (1979): 189-201.
9
votes
1answer
215 views

Vertex isoperimetric number of a graph - NP-hard?

The vertex isoperimetric number of a graph $G=(V,E)$ is $i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\}$. Several academic papers state that the problem of computing ...
10
votes
1answer
257 views

Complexity of checking if two words have an interleaving in a language

For a fixed language $L$ on some alphabet $A$, let us consider the following problem, that I call $L$-INTERLEAVING: Input: two words $u, v \in A^*$ Output: whether there exists an interleaving of $u$ ...
6
votes
0answers
86 views

Looking for an easy/pedantic exposition of Renegar's famous result on polynomial optimization

In September $1989$, Renegar had this famous sequence of 3 papers titled, "On the Computational Complexity and Geometry of the First-order Theory of the Reals, Part I/II/III". I was wondering if ...
0
votes
0answers
119 views

Efficient training algorithm for a generalized version of SVM

In 2014 year we presented a generalized version of the support vector machine that uses family of non-parallel hyperplanes for binary classification. Method easily can be extended to kernel and ...
7
votes
2answers
219 views

Efficiently ordering typed programs

Sometimes it is useful to enumerate in increasing order programs that have a given type. A simple example is test generation for compilers: we want to test a new optimising phase and are ...
5
votes
0answers
111 views

Transferring results on coalgebras in one category to another

Let $F$ and $G$ be endofunctors over categories $C$ and $ D$, respectively. Suppose that there is a forgetful functor $C \to D$ that has a left adjoint. Can we infer properties of $F$-coalgebras ...
3
votes
2answers
172 views

Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

Since every $3$-SAT instance with $n$ variables can be expressed as a degree-$3$ polynomial over $\mathbb{F}_2$ with $n$ unknowns, the NP-hardness of $3$-SAT directly translates to NP-hardness of ...
6
votes
1answer
283 views

Connectivity of a random regular graph of degree $d$

An Erdos-Renyi graph over $n$ vertices and average degree $d$ is not connected whp iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be connected? ...
5
votes
0answers
136 views

More powerful generator than Nisan-Wigderson one

Nisan-Wigderson generator can be computed in $\log^{O(1)} n$ space and fools all constant-depth circuits of size poly($n$). I mean Theorem 5 here. I want another generator, that can be computed in ...
9
votes
1answer
182 views

Where can I find examples of error correcting codes of the following types?

First, apologies if this question is in appropriate or trivial for this site. I'm a physicist looking for some help outside his comfort zone. In PRL 87 167902 (2001) it is claimed that "...for an ...
7
votes
2answers
261 views

Reference for the number of samples needed to distinguish two probability distributions

I am looking for a reference (and/or a full proof) for this statement: $O(1/\epsilon^2)$ samples suffice to distinguish any two probability distributions with variation distance $\epsilon$. I ...
4
votes
1answer
207 views

Word length using entropy : Maximum entropy criteria

The question is based on research paper titled, Markovian language model of the DNA and its information content In the supplementary document, the Authors show how they determine the word length of ...
11
votes
0answers
168 views

Categorical semantics for S5 modal logic?

Does anyone know where I can look to find out what the generally categorical semantics of S5 is? For S4, the answer is well-known: we want a Cartesian closed category with a product-preserving ...
8
votes
1answer
146 views

Intuitionistic fragments of classical logic

For what conditions on P and Q, does P ⊢ Q in classical logic imply ...
9
votes
1answer
120 views

About the origin of the names “immune” and “simple”

I have been wondering for a while about the origin of the names "immune" and "simple". I also posed the same question to Andrea Sorbi, who in turn involved a few more colleagues in the discussion. ...
9
votes
0answers
174 views

Is there a known automatic proof of the independence of the continuum hypothesis?

In 2002, L.C. Paulson gave a mechanized proof of the consistency of the axiom of choice by formalizing $V=L$ and its consistency. We could ask whether there is a formalized proof of the independence ...
3
votes
0answers
56 views

Decidability of the monadic second-order theory of a class of finite structures

Let $L$ be the set of sentences in some logic. I am interested in cases where $L$ is the set of sentences in monadic second-order logic, or it is its $\Pi^1_1$ fragment. Let $K$ be a class of finite ...
6
votes
0answers
74 views

Reference request for a $\Delta_2^P$ satisfiability problem

I am looking for the name and a reference for a $\Delta_2^P$-complete problem that looks like the following Input: A collection of CNF formulas $\phi_i(x_1^i, x_2^i,\dots, x_m^i, z_1, z_2, \dots, z_{...
6
votes
2answers
227 views

ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$

The PCP theorem can be stated like this : There is a polynomial time reduction from SAT to $Gap\text-MAX\text-3SAT_{c}$ i.e. there is a reduction that maps an instance $\phi$ of SAT to an instance $...
5
votes
1answer
189 views

Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time?

This question is about subset problems (the solution is a subset of the instance, so trivially enumerable in $2^n \cdot n^c$ time), and the parameter is the solution size, so-called the standard ...
4
votes
1answer
577 views

Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?

It is known that Exact Set Cover is an NP-hard problem (Reduction from 3-SAT and 3-Coloring). Also, my minor analysis one can realize that this problem is also ETH-hard, i.e. this cannot be solved in ...
10
votes
1answer
263 views

Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?

Let $HALT_n$ denote the string of length $2^n$ corresponding to the truth table of the halting problem for inputs of length $n$. If the sequence of Kolmogorov complexities $K(HALT_n)$ were $O(1)$, ...
5
votes
1answer
120 views

If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$

I'm searching for a reference for the following property: Fact. Let $u, v \in A^*$. Write $w$ for the primitive root of $u\cdot v$, i.e., $u\cdot v = w^c$. There are unique words $z, z'$ such ...
5
votes
1answer
63 views

Reference needed for lower bound on number of guards in three-dimensional art gallery guarding

During my research (writing my master's thesis) I've stumbled across the book Art Gallery Theorems and Algorithms by O’Rourke. In chapter 10 (pdf available on the above site), section 10.2.2. he shows ...
4
votes
1answer
295 views

Math foundation for namespace problem

TLDR; What is the mathematics foundation for the namespace problem? Can I reduce namespace problem to set theory or other math concepts/objects (lambda calculus, category theory)? I'm doing an ...
9
votes
1answer
247 views

Is there a name for this concept in Communication Complexity?

Let Alice and Bob compute boolean function $f(x_1,\dots,x_{2n})$. Select a random subset $\mathcal I\subseteq\{1,\dots,2n\}$ of cardinality $n$ and let $\mathcal J=\{1,\dots,2n\}\backslash\mathcal I$....
3
votes
3answers
161 views

Approaches for Theoretical Analysis of Estimates of Probability Distributions

Consider that you have a probability distribution p of some quantity X and you have obtained (via some algorithm) an estimate q of p according to some definition of closeness. Are there methods/papers ...
0
votes
0answers
71 views

Constructing non-residues from irreducible polynomials

Given, $r|p-1$; Can we construct $r^{th}$ non-residue given an irreducible polynomial $f(x) \in \mathbb{F}_p[x]$ of degree $r$. Any reference would be of great help.
5
votes
2answers
146 views

Complexity of Uniform Generation of Perfect Matchings

Jerrum,Valiant and Vazirani on their paper "Random generation of combinatorial structures from a uniform" (http://www.cc.gatech.edu/~vazirani/AppCount.pdf) talk about seeing problems related to ...
6
votes
2answers
175 views

Given a type system T, and a type $A$ in that type system, is there an (effective) surjection from $\mathbb{N}$ onto the set of terms of that type?

I assume that in hoping for an effective bijection, we run into undecidability issues, but intuitively, it seems like there should at least be a surjection from $\mathbb{N}$ to the terms of any type, ...
9
votes
1answer
174 views

Regular languages and constant communication complexity

Let $L \subseteq A^*$ be a language, and define $f_L\colon A^* \times A^* \to \{0, 1\}$ by $f_L(x, y) = 1$ iff $x\cdot y \in L$. I'm searching for a reference for: Proposition. $L$ is regular iff ...
1
vote
1answer
143 views

How to find the “best vectors” in a given matrix whose sum of products is as small as possible?

The input is a matrix $\mathbf{A}=[a_{ij}]$ of real numbers $a_{ij}>0$ for all $i\in\{1,\ldots,k\}$ and $j\in\{1,\ldots,n\}$ and a real number $v$. The coefficient of the matrix are not all greater ...
12
votes
1answer
321 views

What is the name of a function $f$ such that $f(x,y) \in L \iff x\in L \wedge y \in L$?

Let $L$ be a language and $f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\star$ a function on two parameters with the property that for all $x$ and $y$, $f$ returns an element of $L$ if and only ...
9
votes
2answers
210 views

Nonstandard dual parametrization of graph problems

One fundamental result in parameterized complexity of graph problems is that VERTEX COVER parameterized by the solution size $k$ is fixed-parameter-tractable (FPT). On the other hand, when ...
17
votes
0answers
192 views

What is the background in algebraic geometry and representation theory needed for geometric complexity theory? [duplicate]

I'm a mathematics student in my junior year and I'm interested in computational complexity and specially geometric complexity theory. I'm going to learn algebraic geometry and representation theory ...
12
votes
1answer
274 views

Generalization of Dilworth's theorem for labeled DAGs

An antichain in a DAG $(V, E)$ is a subset $A \subseteq V$ of vertices that are pairwise unreachable, namely, there are no $v \neq v' \in A$ such that $v$ is reachable from $v'$ in $E$. From Dilworth'...
8
votes
0answers
81 views

Complexity of computing the simplicial width of a graph

Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that: For every edge $\{v_1,v_2\} \in E$, there ...
4
votes
1answer
109 views

Shortest cycle separator for biconnected planar graphs

An $(s,f)$- balanced separator in a graph $G$ is a set $S$ of $s$ vertices removing which yields connected compoennts of size at most $f|V|$. If the vertices of $S$ form a cycle of length $s$, $S$ is ...
1
vote
0answers
87 views

Is there a signature of a first-order language that characterize the class of regular languages?

A previous question on this site was about extending the first-order logic with logical constants (quantifiers, fixed-point operators, etc.) to obtain a logical characterization of the class of ...
6
votes
1answer
260 views

Average-case complexity open problems other than one-way functions

The list of unsolved problems in computer science on Wikipedia lists no problems in average-case complexity, except "Do one-way functions exist?" which is whether there is a polynomial time computable ...
14
votes
2answers
379 views

Pair of vertex disjoint cycles in a directed graph

What is the fastest known deterministic algorithm that can recognize directed graphs with a pair of vertex disjoint cycles? I know graphs with min outdegree three always have such a pair (Thomassen'83)...
17
votes
2answers
229 views

A reference for a “more algebraic” approach to pushdown automata and CFLs?

In the Sakarovitch's book on automata theory, it is written in the introduction to the section on rationals in the free group that the material presented therein lays "the foundation of a truly ...
10
votes
1answer
304 views

Pattern matching with don't cares: multiple patterns

Kalai's 2-page SODA paper gives a simple and efficient algorithm for pattern matching with don't cares (wildcards that match one character). In essence, it is as easy as convolution. But what happens ...
7
votes
2answers
165 views

Finite Automata with succinct representation of chains of states

Consider a kind of automata similar to common DFAs or NFAs where it is possible to represent succinctly linear chains of states. In other words, an automaton like this: could be represented in this ...
1
vote
1answer
118 views

K-fold Traveling salesman problem - A variant of TSP

Consider a weighted graph $K_n$ and where the weights between vertices $i,j$ is $w_{ij}$. Consider a path, $\sigma$, passing through each vertex only once. Here $\sigma_i$ is the vertex in the $(i\%n)^...