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
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 ...
Andrea's user avatar
  • 319
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$ ...
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
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 ...
pyridoxal_trigeminus's user avatar
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 ...
Marzio De Biasi's user avatar
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 ...
StubbornSnail's user avatar
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 ...
user72031's user avatar
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 ...
Brett's user avatar
  • 33
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, ...
Mengfan Ma's user avatar
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 ...
Russell Easterly's user avatar
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 ...
Daniel García's user avatar
-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}$. ...
S. M.'s user avatar
  • 109
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&...
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
  • 13.9k
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$) ...
Erel Segal-Halevi's user avatar
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 ...
S. M.'s user avatar
  • 109
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 ...
S. M.'s user avatar
  • 109
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) ...
a3nm's user avatar
  • 9,259
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]$. ...
Chao Xu's user avatar
  • 4,399
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$,...
user71821's user avatar
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 ...
sparusaurata's user avatar
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 ...
Michael C.'s user avatar
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 ...
TomKern's user avatar
  • 429
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 ...
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
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 ...
Soha's user avatar
  • 187
-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 $...
Samdney's user avatar
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 ...
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
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$ (...
hedgehog0's user avatar
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 ...
user2316602's user avatar
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 ...
Anton Ehrmanntraut's user avatar
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 \...
Erel Segal-Halevi's user avatar
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 ...
Soha's user avatar
  • 187
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 ...
Jxb's user avatar
  • 316
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 ...
Evan Aad's user avatar
  • 354
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 ...
Nicola Gigante's user avatar
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*}...
sd234's user avatar
  • 575
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 ...
LiminalSpace's user avatar
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 ...
Per Alexandersson's user avatar
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{...
Thomas Ahle's user avatar
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 ...
EGME's user avatar
  • 161
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. ...
user3483902's user avatar
  • 1,201
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 ...
Soha's user avatar
  • 187
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 ...
Amor Rei's user avatar
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 ...
FxMySz's user avatar
  • 131
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, ...
Nicola Gigante's user avatar
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 ...
Blanco's user avatar
  • 421

1
2 3 4 5
33