Skip to main content

Questions tagged [reference-request]

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

Filter by
Sorted by
Tagged with
11 votes
1 answer
180 views

Computational complexity of the elementary theory of finite fields

Let $T_f$ denote the set of first-order sentences in the language of rings which are true in all the finite fields. That is, $T_f = \{\varphi \mid K \models \varphi, \text{ for every finite field } K\}...
19 votes
2 answers
2k views

Gentle introduction to graph isomorphism for bounded valance graphs

I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained here. But I found it ...
0 votes
0 answers
78 views

Channel Capacity & Dependency Graph

A single-input-single-output communication channel is to be used repetitively. Denote by $X_i \in \mathcal X$ the input at time $i$ and by $Y_i \in \mathcal Y$ the output at time $i$. Assume the ...
5 votes
0 answers
74 views

A split-consistency property of a formal language

I am looking for occurrences in literature of the following property of a formal language $\mathcal L$ over an alphabet $\Sigma$ For any quadruple of words $a,b,c,d\in\Sigma^*$, if $ac,bc,ad\in\...
4 votes
1 answer
98 views

Smoothed analysis in the Turing machine model

Smoothed analysis is usually defined using real numbers: given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it ...
1 vote
0 answers
154 views

In what paper did Dijkstra say "with your hands in your pockets"?

I'm looking for a paper by Edsger Dijkstra (which I've read before) in which he talks about a certain mathematical argument that I can't quite remember what it was, but it was an elementary strategy ...
5 votes
2 answers
201 views

The empty tree-word for regular tree languages

Are there references that consider the "empty tree-word" as an allowable element of regular languages of trees? Are there situations where it is more sensible to allow an empty tree-word? ...
8 votes
0 answers
366 views

What exactly did Lenstra prove on mixed integer linear program?

I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
4 votes
1 answer
130 views

Constructing vector valued boolean circuits from boolean circuits

This is a reference request. I'm interested in the compositional construction of small boolean circuits for vector-valued boolean functions $\phi : \mathbb{B}^m \rightarrow \mathbb{B}^n$ for $n >...
1 vote
0 answers
62 views

Is this kind of "multi-reduction" interesting?

Given a decision problem $P$, the usual way to show that it is NP-hard is to find a known NP-hard problem $Q$, and show a polynomial-time algorithm that transforms every instance $I_Q$ of $Q$ to an ...
3 votes
0 answers
47 views

Cuthill - Mckee Guarantees?

I'm interested in the following problem: given $M$, a $p \times p $ symmetric sparse matrix (the number of non-zero elements in each row is at most $s \ll p$), find a matrix $B = PMP^T$ where $P$ is a ...
6 votes
0 answers
66 views

Böhm tree with pairs (product types)

I am looking for references for a notion of Böhm tree for the λ-calculus with pairs and projections (and the reduction rule $\pi_i\, \langle t_1, t_2\rangle \longrightarrow t_i$). I'm only aware of ...
5 votes
1 answer
185 views

What is the probability a random language in $\mathsf{PSPACE}$ is in $\mathsf{P}$?

Suppose I am drawing a venn diagram of complexity classes, and I don't want one that is the most visually pleasing, but the most accurate. How much of PSPACE should P take up? Let $L$ be chosen ...
14 votes
2 answers
1k views

Sufficient conditions for the regularity of a context-free language

It would be nice to collect a list of conditions that imply that a context-free language L is regular, i.e. conditions of the form: "if a given CFG/PDA has property P, then its languages is regular" ...
13 votes
4 answers
837 views

A Multi-cut Problem

I'm looking for a name or any references to this problem. Given a weighted graph $G = (V, E, w)$ find a partition of the vertices into up to $n = |V|$ sets $S_1,\ldots,S_n$ so as to maximize the ...
1 vote
0 answers
95 views

Induced subgraphs with interface

I am interested in hypergraphs with interfaces, I'll call them simply "graphs" in the following. Formally, a graph of sort $k$ is a tuple $(V,E,i)$ with $E\subseteq V^+$ is the set of edges, ...
4 votes
1 answer
117 views

Straight-line program for sets

Let $\mathcal{S}$ be a collection of sets. A set straight-line program that enumerates $\mathcal{S}$ is a sequence of sets $B_1,\ldots,B_m$, such that $\mathcal{S}\subseteq \{B_1,\ldots,B_m\}$. For ...
5 votes
0 answers
73 views

Hardness of Computing Tribes-DNF by Decision Trees

In this paper on "The Polynomial Hierarchy, Random Oracles, and Boolean Circuits", Fact (3.2) states that it is impossible for a polylogarithmic depth decision tree to compute the Tribes-DNF ...
4 votes
0 answers
135 views

Learning a regular language with a specified closure property

Consider an alphabet $\Sigma$, and a partial transformation function $f:S\to\Sigma^\ast$ defined on some subset $S\subseteq\Sigma^\ast$. Let $S_f$ denote the set of strings $s\in S$ such that $f^n(s)\...
10 votes
2 answers
641 views

Complexity of NFA cofiniteness

What is the complexity, given as input an NFA, of determining if it is cofinite (i.e., the complement of its language is finite)? Surely this must be known but I can't find a reference. Note that the ...
1 vote
0 answers
41 views

Convergence rates for the iterates of SGD on Lipschitz convex functions

Let $f:X \rightarrow \mathbb{R}$ be a convex and $L$-Lipschitz continuous function. Suppose $f^* = \min_{x \in X} f(x) \in \mathbb{R}$ and let $X^* = \{x \in X : f(x) = f^*\}$. For a non-negative ...
7 votes
0 answers
101 views

Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned: Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ ...
9 votes
3 answers
307 views

Cheap online selection with weighted comparisons

Suppose we want to find the smallest element of a set $S$, whose elements are indexed from $1$ to $n$. We do not have access to the values of these elements, but we can compare any two elements of $S$...
0 votes
0 answers
21 views

Detection of intersection between two $d$-dimensional convex polytopes with at most $N$ facets

I am looking for a reference on the current state-of-the-art algorithm(s) for detecting intersection between two $d$-dimensional convex polytopes, with time complexity depending on their number of ...
2 votes
0 answers
76 views

References for algorithms to compute approximating polytopes for arbitrary convex sets

There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes. One of the main results in this area is that under some mild ...
2 votes
0 answers
41 views

Characterization of CF languages closed under circular shifts

Along the same lines as what was asked in this post: Is there a simple characterization of regular languages closed under circular shifts? Are there simple characterizations/properties of Context Free ...
3 votes
1 answer
226 views

Horn clause on cnf

Recall that a CNF formula is Horn if each clause contains at most one positive literal. Is it possible any unsatisfiable Horn CNF formula has a polynomial-size treelike Resolution refutation? Is there ...
2 votes
0 answers
40 views

Homeomorphic subtree extraction in integer sorting time

Background Given a rooted, binary tree $T$ with leaves bijectively labeled by $\{1, \ldots, n\}$ (a "phylogenetic tree"). Let $L \subseteq \{1, \ldots, n\}$, and $|L| = k$. The homeomorphic ...
3 votes
0 answers
88 views

Learning discrete math for research

This might be an unusual question, but please bear with me. As a graduate student in mathematics, I haven't delved deeply into several discrete math subjects relevant to research in theoretical ...
5 votes
1 answer
256 views

How many numbers are needed such that the possible subset sums cover $\{1, \frac{1}{2}, \frac{1}{3},\dots, \frac{1}{2^m}\}$?

For a multiset $N$ of positive numbers, the set of possible subset sums is $f(N)=\{s\in \mathbb{R}: \exists S\in 2^N, s=\sum_{a\in S} a\}$. We say $N$ generates $T$ if $T\subseteq f(N)$. For example, ...
-1 votes
1 answer
191 views

Calculation on Sparsification and critical clauses in SAT

I followed from this question. I need to prove, the final result $s_k \leq (1 − \Omega(k^{−1}))s_{\infty}.$ But before prove the final result first I need to prove the $s_k \leq (1 − d/k))s_{\infty}$. ...
1 vote
0 answers
49 views

Short learned clauses for XSAT

Are there any studies about how effective a limited resolution pre-processor is for DPLL-CDCL type SAT solvers? By limited resolution pre-processor I mean a pre-processor that generates short (1,2, or ...
5 votes
1 answer
194 views

What infinite sums cannot be approximated in polynomial time?

The following is from the book Geometric algorithms and combinatorial optimization: It shows an infinite sum that has an FPTAS (= an $\epsilon$-approximation can be computed using poly($1/\epsilon$) ...
2 votes
0 answers
81 views

On The Complexity of Block-Interchange Distance for Binary Strings

The block-interchange distance problem is defined as finding the minimal number of subsequences swaps to apply to an input string to turn it into a desired string. It is a well studied tractable ...
1 vote
1 answer
323 views

Sparsification and critical clauses in SAT

I have been studying the Exponential-Time Hypothesis, ETH, from this paper, there defined $s_k = \inf\{\delta \geq 0 | k\text{-}SAT \in RTIME[2^{\delta n}]\}$. But in that paper's page number 10, I ...
2 votes
0 answers
151 views

What is best lower bound for comparison sort?

Sorting $n$ numbers requires $\lceil \log_2(n!)\rceil$ comparisons and this is asymptotically optimal, but there is an $O(n)$ error term. What is the best known lower bound for large $n$? I couldn't ...
3 votes
1 answer
228 views

Operation on Sub-exponential Reduction

I have a question concerning the SERF-reducibility of Impagliazzo, Paturi and Zane and subexponential algorithms. My question is: is a composition of two SERF reductions a SERF reduction? Are there a ...
2 votes
1 answer
132 views

Approaches to fast matrix multiplication and their limits

Let $\omega$ be the smallest constant so that we can do matrix multiplication in complexity $n^{\omega+o(1)}$. I am wondering what are the known avenues which establish the non-trivial bound $\omega&...
6 votes
1 answer
166 views

Tree decompositions with unique witness for each edge

In this question I am concerned with tree decompositions of undirected graphs. Recall that a tree decomposition of a graph $G = (V, E)$ is a tree $T$ whose nodes are subsets of $V$ (called bags) ...
5 votes
1 answer
176 views

Survey on Erdős-Pósa?

Does anyone know of any good surveys on Erdős-Pósa? I am particularly interested in what are the latest results for the bounding function for directed and even cycles in planar and minor free graphs ...
5 votes
2 answers
611 views

Maximum Treewidth of a Graph with $m$ Edges

What is the maximum treewidth of a graph with $m$ edges? In other words, what is the correct growth for the following function? $\alpha(m) = max\{\mathrm{treewidth}(G): G \mbox{ has $m$ edges}\}$. ...
7 votes
1 answer
587 views

Connectivity of a random regular graph of degree $d$

An Erdős–Rényi graph over $n$ vertices and average degree $d$ is not connected w.h.p. iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be ...
3 votes
1 answer
136 views

Rearrange vectors so partial sums are all non-negative

Consider we are given a collection of $n$ vectors in $d$ dimensions, we want to decide if they can be rearranged into $v_1,\ldots,v_n$ such that $\sum_{i=1}^j v_i\geq \textbf{0}$ for all $j\in [n]$. ...
1 vote
0 answers
41 views

NP-hardness of partitioning into k sets [closed]

Given a multiset $S$ of positive integers and a fixed positive integer $k$, can $S$ be partitioned into $k$ parts with equal sum? For $k = 2$, this is the well-known Partition problem. For general $k$,...
11 votes
2 answers
370 views

What are pertinent references to cite on Scott domains?

Scott domains are often presented as having been introduced in 1969. However, the first (but numerous!) papers are from the 1970s, so it is not easy to know what the pertinent references are. My two ...
1 vote
1 answer
109 views

A variant of the generalised assignment problem

I am trying to solve this problem: There are $N$ workers and $T$ tasks. Each task can be assigned to at most one worker. Each worker can be assigned any number of tasks. The profit obtained by ...
2 votes
0 answers
79 views

Is there a text that contains all 4 Büchi-Elgot-Trakhtenbrot-style theorems?

There are several natural Büchi-Elgot-Trakhtenbrot-style theorems: The equivalence of various finite automata on finite words and the weak monadic second order theory of 1 successor The equivalence ...
3 votes
0 answers
77 views

What is $\mathrm{NC}^0$-uniform reduction

I am interesting in strict and ``right'' formulations of results about $\mathrm{NC}^1$-completeness of some languages. Consider for example Barrington's theorem about $\mathrm{NC}^1$-completeness of ...
4 votes
0 answers
143 views

Maximum volume ellipsoid in an intersection of ellipsoids

Given a collection of $m$ ellipsoids in $\Bbb R^n$, compute the maximum volume ellipsoid inscribed in their intersection. In section 8.4.2 of Boyd & Vandenberghe's Convex Optimization, this ...
1 vote
0 answers
83 views

Is the Category of $(* \to)^n *$-kinded types freely generated from the discrete graph with $n$ nodes?

In Introduction to Higher Order Categorical Logic part 1, section 4, Lambek defines an adjunction between $\mathbf{Graph}$, the category of graphs and graph homomorphisms, and the category of ...

1
2 3 4 5
33