Questions tagged [reference-request]

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

3
votes
2answers
192 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 ...
5
votes
1answer
335 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? ...
4
votes
0answers
138 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 ...
8
votes
1answer
186 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 ...
6
votes
2answers
316 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
225 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
185 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 ...
7
votes
1answer
149 views

Intuitionistic fragments of classical logic

For what conditions on P and Q, does P ⊢ Q in classical logic imply ...
8
votes
1answer
122 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. ...
8
votes
0answers
179 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 ...
2
votes
0answers
57 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 ...
5
votes
0answers
75 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_{...
5
votes
2answers
241 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 $...
4
votes
1answer
191 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 ...
5
votes
1answer
648 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 ...
9
votes
1answer
291 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)$, ...
4
votes
1answer
131 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 ...
4
votes
1answer
65 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 ...
3
votes
1answer
297 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 ...
8
votes
1answer
255 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
167 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 ...
4
votes
2answers
156 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 ...
5
votes
2answers
182 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
181 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
144 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 ...
11
votes
1answer
326 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 ...
8
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 ...
16
votes
0answers
194 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 ...
11
votes
1answer
286 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'...
7
votes
0answers
85 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 ...
3
votes
1answer
110 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
89 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 ...
5
votes
1answer
262 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 ...
13
votes
2answers
384 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
236 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 ...
9
votes
1answer
323 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 ...
6
votes
2answers
170 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
119 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)^...
2
votes
1answer
157 views

Probability of random variable $X$ less than $max(Y_i)$

For $\lambda > \mu$, consider independent random variables (i) $X \sim Pois(\mu)$ and (ii) $Y_i \sim Pois(\lambda),\;i\in{1,2}$. Question : Can we upper-bound the following? $$\mathbb{P}\big(X\...
3
votes
1answer
217 views

Constructing subfields of a finite field

Suppose we have a finite field $\mathbb{F}_{p^n} = \frac{\mathbb{F}_{p}[x]}{<f(x)>}$. I want a deterministic polynomial algorithm to compute all subfields of this field. I think we can do ...
20
votes
5answers
672 views

Easy problems with hard counting versions

Wikipedia provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-...
3
votes
0answers
128 views

Maximize number of edges covered by an independent set of vertices

Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to ...
8
votes
0answers
294 views

Complexity of $k=2$ set packing

I am interested in the best currently known algorithm (in fact, any relevant reference) for the following problem: Given a family of subsets $S_1,S_2,\ldots S_N\subseteq \{1,2,\ldots N\}$, ...
1
vote
1answer
91 views

Properties of convex polytope of 0-1 matrices

Problem setting Consider a set $ S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$. Consider a $k\times k$ matrix $M$ ...
10
votes
1answer
230 views

Complexity of reachability in linear dynamical systems over finite fields

Let $A$ be a matrix over the finite field $\mathbb{F}_2 = \{0,1\}$ and $x$, $y$ be vectors of the space $\mathbb{F}_2^n$. I am interested in the computational complexity of deciding whether there ...
5
votes
0answers
138 views

Notions of Computability at Higher Type III

I've recently found a very nice survey paper called "Notions of Computability at Higher Type" by John R. Longley. The paper says it is part of a 3-part series, with the 3rd concerning non-extensional ...
7
votes
1answer
288 views

Minimum Spanning tree on a complete “random” graph

Consider a complete undirected graph with $n$ vertices, $K_n$. Let weight of an edge between vertices $i\; \& \;j$ be a random variable $E_{ij}$. Let $E_{ij} \sim exp(\lambda)$, where $exp(\lambda)...
2
votes
0answers
93 views

Minimize the product of distances from n fixed points

Given $n$ fixed points $\{p_i\}_{i=1}^n$ in $D$-dimensional Euclidean space $\mathbb{R}^D$, consider the following optimization problem: $$ \begin{align} \text{mininize} \ \ \ &\prod_{i=1}^n \...
6
votes
1answer
199 views

Number of solutions for a system of linear equations over a finite ring

Let $R$ be a finite ring with operations $(+,\cdot)$. Let $A \in R^{m\times n}$ and $b\in R^{m}$. Questions: What is the complexity of counting the number of solutions to the system of equations $...
7
votes
1answer
152 views

What are the hardness results known for CSP over $\mathbb{F}_q$?

I found two related papers, There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf A kind of a stronger result might be found in these two other papers, http://...