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
5 votes
0 answers
72 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\...
Gejza Jenča's user avatar
4 votes
1 answer
95 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 ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
148 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 ...
user72699's user avatar
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 ...
Euclid's user avatar
  • 1
4 votes
1 answer
129 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 >...
Martin Berger's user avatar
1 vote
0 answers
61 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 ...
Erel Segal-Halevi's user avatar
5 votes
2 answers
200 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? ...
TomKern's user avatar
  • 489
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 ...
WeakLearner's user avatar
6 votes
0 answers
65 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 ...
Lê Thành Dũng 'Tito' Nguyễn's user avatar
5 votes
1 answer
183 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 ...
abrahimladha's user avatar
4 votes
1 answer
116 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 ...
Chao Xu's user avatar
  • 4,479
1 vote
0 answers
93 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, ...
Denis's user avatar
  • 8,903
5 votes
0 answers
72 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 ...
CHLander's user avatar
4 votes
0 answers
134 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)\...
LegionMammal978's user avatar
10 votes
2 answers
638 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 ...
M.Monet's user avatar
  • 1,429
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 ...
Andrea's user avatar
  • 319
7 votes
0 answers
99 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$ ...
user11718766's user avatar
0 votes
0 answers
20 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 ...
pyridoxal_trigeminus's user avatar
2 votes
0 answers
75 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 ...
pyridoxal_trigeminus's user avatar
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 ...
Marzio De Biasi's user avatar
2 votes
0 answers
38 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 ...
StubbornSnail's user avatar
3 votes
0 answers
85 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 ...
user72031's user avatar
3 votes
1 answer
221 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 ...
HDD's user avatar
  • 133
5 votes
1 answer
255 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, ...
Mengfan Ma's user avatar
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 ...
Russell Easterly's user avatar
2 votes
0 answers
80 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 ...
Daniel García's user avatar
-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}$. ...
S. M.'s user avatar
  • 109
2 votes
1 answer
130 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&...
Zach Hunter's user avatar
2 votes
0 answers
150 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 ...
domotorp's user avatar
  • 14k
5 votes
1 answer
193 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$) ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
322 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 ...
S. M.'s user avatar
  • 109
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 ...
S. M.'s user avatar
  • 109
6 votes
1 answer
163 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) ...
a3nm's user avatar
  • 9,517
3 votes
1 answer
135 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]$. ...
Chao Xu's user avatar
  • 4,479
1 vote
0 answers
40 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$,...
user71821's user avatar
11 votes
2 answers
368 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 ...
sparusaurata's user avatar
1 vote
1 answer
108 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 ...
Michael C.'s user avatar
2 votes
0 answers
77 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 ...
TomKern's user avatar
  • 489
3 votes
0 answers
76 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 ...
Alexey Milovanov's user avatar
1 vote
0 answers
82 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 ...
Johan Thiborg-Ericson's user avatar
17 votes
2 answers
1k views

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$. A literal of variable $x$ is an expression of the form $x\...
Junqiang Peng's user avatar
1 vote
1 answer
86 views

Learning arithmetic series

Let us say that an arithmetic series is a series of the form $s_t = \{0, t, 2t, \ldots\}$. For example, $s_3 = \{0, 3, 6, \ldots\}$. Now consider the concept class composed of all arithmetic series of ...
user avatar
4 votes
2 answers
561 views

Do we currently know a polynomial-size Frege proof for Tseitin formulas?

There's a vast literature about super-polynomial lower bounds on proof lengths of Tseitin formulas in bounded-depth Frege systems, but what I'm curious about is: what if we don't restrict the depth of ...
Soha's user avatar
  • 187
-1 votes
1 answer
87 views

Representation of binary strings by graphs and hypergraphs

Let $\Sigma$ be the set $\{ 0, 1 \}$, then the set of all finite binary strings of length $n$ is written as $\Sigma^{\star}_{n}$. Question: Which further ways of representing binary strings of length $...
Samdney's user avatar
0 votes
1 answer
131 views

Finding deepest intersection

There must be a name for this problem, but I can't find it: Given $n$ rectangles in the plane, what is the most number of rectangles that a point in the plane belongs to? In other words, thinking of ...
femeve3881's user avatar
1 vote
0 answers
36 views

First-order linear mu-calculus?

There is linear $\mu$-calculus (see e.g. [1]) and first-order $\mu$-calculus (see e.g. here). Has anybody studied first-order linear $\mu$-calculus? [1]: Christian Dax, Martin Hofmann, Martin Lange: A ...
Nicola Gigante's user avatar
0 votes
0 answers
56 views

Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?

The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here: Consider a probabilistic Turing Machine (PTM) $M$, and a language $L \in BPP$: If $x \in L$ (...
hedgehog0's user avatar
2 votes
0 answers
54 views

Approximately sampling from a discrete unimodal distribution with large support

I have an algorithmic problem and I am curious if a solution is known in the literature, because I cannot find it. I came up with an algorithm of my own, but would be curious if something is known. I ...
user2316602's user avatar
3 votes
0 answers
110 views

How does NP-completess of decision problems relate to NP-completeness of search problems?

Background Oded Goldreich differentiates in his textbook (Computational Complexity: A Conceptual Perspective) between the "decision" variant of NP problems and "search" variant of ...
Anton Ehrmanntraut's user avatar
6 votes
0 answers
288 views

Techniques for solving huge linear programs

During the solution of some computational problem, we have arrived at a linear program of the following form: \begin{align*} \text{maximize} ~~ c x \\ \text{subject to} ~~ A x \leq b, x \geq 0 \...
Erel Segal-Halevi's user avatar

1
2 3 4 5
33