Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,626
questions
1
vote
0
answers
33
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
89
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$ ...
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 ...
2
votes
0
answers
74
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
35
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 ...
2
votes
0
answers
36
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
82
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 ...
3
votes
1
answer
198
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 ...
5
votes
1
answer
247
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
vote
0
answers
48
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 ...
2
votes
0
answers
77
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
votes
1
answer
184
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}$.
...
2
votes
1
answer
119
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&...
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 ...
5
votes
1
answer
182
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$) ...
1
vote
1
answer
320
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 ...
3
votes
1
answer
225
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 ...
6
votes
1
answer
152
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) ...
3
votes
1
answer
121
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
39
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$,...
10
votes
2
answers
348
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
95
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
73
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
65
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 ...
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 ...
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\...
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 ...
4
votes
2
answers
551
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 ...
-1
votes
1
answer
77
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 $...
0
votes
1
answer
128
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 ...
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 ...
0
votes
0
answers
52
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$ (...
2
votes
0
answers
53
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 ...
3
votes
0
answers
109
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 ...
6
votes
0
answers
277
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
\...
4
votes
1
answer
104
views
Power of non-implicationally-complete Frege systems and Boolean equational calculus
We know that Frege systems are required to be implicationally complete -- namely, if a set of formulas $B_1,B_2,\cdots,B_t$ imply formula $C$, then this implication can be proven in the system. I'm ...
4
votes
1
answer
91
views
Methods for Determining the minimal Width of Resolution Refutations for CNF Formulas
Recall that the width of a resolution refutation $R$ of a CNF formula $F$ is the maximal number of literals in any clause occurring in $R$. I am intersting in finding the minimal width of some certain ...
2
votes
0
answers
52
views
Formal semantics of a simple object oriented language without inheritance but with self-referential objects
Would you please point me to some papers or textbooks that describe rigorously a formal semantics/computational model of a simple object-oriented language? The language needs not accommodate ...
4
votes
1
answer
54
views
References on second-order quantifier elimination and related topics
I was wondering whether something like elimination of second-order quantifiers exist, and indeed it seems it does. I've found there's a workshop on this topic, and the webpage describes exactly what I ...
2
votes
2
answers
127
views
Linear Programming Sensitivity to Matrix
Consider a linear program in the following standard form:
\begin{align*}
&\max c^T x &\\
&\mbox{subject to:}\\
&A x \preceq b\\
&x \succeq 0
\end{align*}
Its dual is
\begin{align*}...
6
votes
3
answers
351
views
Structural Complexity Theory References
I'm a PhD student in mathematics (mostly studying algebraic geometry), but I've always been interested in computational complexity theory.
As an undergraduate, I completed an independent reading ...
21
votes
10
answers
3k
views
What are examples of recent relatively simple 'toolbox algorithms'?
Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc.
There are also several relatively standard data structures, such ...
6
votes
1
answer
349
views
Condition Number dependent algorithms for matrix operations
Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
6
votes
2
answers
626
views
NP-complete problems where the inputs are prime numbers
Are there (well?) known NP-complete problems where the input(s) is(are) a(some) prime number(s), with complexity measured relative to the binary length of the input number(s)? I am thinking there are ...
7
votes
0
answers
212
views
Relationships between Descriptive Complexity and Average Case Complexity
Descriptive complexity gives one a logic or at least a logic to express languages in a complexity class. The PH can be defined as the union of all classes that can be expressed in Second order logic. ...
2
votes
0
answers
73
views
Proof systems that may be stronger than extended Frege?
The extended Frege proof system is thought to be a fairly strong proof system, with no known superpolynomial lower bounds. But I wonder, if extended Frege is proved not to be polynomially bounded one ...
0
votes
0
answers
17
views
Reference Request : For a paper on resolving conflicts in Interpretability methods
Well , this post is going to sound a bit similar to crush pages , where people post where and when they had seen someone and ask other people if they can help in identifying that person or this post ...
13
votes
2
answers
373
views
General collection with the current state of complexity bounds of well-known unsolved problems?
Most classical computer science problems are still open concerning the exact asymptotic algorithmic worst-case complexity required to solve them.
Is there any online collaborative wiki (or other ...
0
votes
0
answers
79
views
Original references for Karp-Lipton theorem improvement by Sipser
The Wikipedia article about the Karp-Lipton theorem ($NP\subseteq P/poly$ implies $\Sigma_2=\Pi_2$), says the following:
The Karp–Lipton theorem is named after Richard M. Karp and Richard J.
Lipton, ...
1
vote
2
answers
100
views
Is Maximum Independent Set polynomial-time solvable in $(p,1)$-colorable graphs for general $p$?
It is well-known that Maximum Independent Set (MIS) in bipartite graphs is polynomial-time solvable.
What happens if we generalize the input graphs by replacing the vertices in one partite with ...