Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,603
questions
-1
votes
0
answers
77
views
Proof for Upper Bound on the Size of the Sum of Rational Numbers
In [1], Dominik Wojtczak determines that the 0-1 SUBSET-SUM problem with non-negative rational numbers is strongly NP-Complete.
Assume we are given a list of n items with
rational non-negative ...
2
votes
0
answers
48
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 ...
16
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\...
- 163
1
vote
1
answer
78
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 ...
- 21
4
votes
2
answers
520
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 ...
- 145
-1
votes
1
answer
74
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 $...
- 1
0
votes
1
answer
123
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 ...
- 1,588
0
votes
0
answers
46
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 ...
- 630
3
votes
0
answers
103
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
270
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
\...
- 2,086
4
votes
1
answer
97
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 ...
- 145
4
votes
1
answer
84
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 ...
- 315
2
votes
0
answers
51
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 ...
- 354
4
votes
1
answer
52
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 ...
- 1,588
2
votes
2
answers
113
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*}...
- 575
6
votes
3
answers
328
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 ...
- 113
20
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
342
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{...
- 958
6
votes
2
answers
609
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 ...
- 161
7
votes
0
answers
188
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. ...
- 1,181
2
votes
0
answers
71
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 ...
- 145
0
votes
0
answers
16
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 ...
- 1
13
votes
2
answers
370
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 ...
- 131
0
votes
0
answers
75
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,588
1
vote
2
answers
95
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 ...
- 421
1
vote
0
answers
49
views
Bound on the treewidth of a graph from modular contraction
I cannot find a reference for this easy to prove result concerning the treewidth of a graph with respect to the treewidth of a modular contraction of it.
Let $G=(V,E)$ be a graph. A module $M \...
- 2,164
3
votes
1
answer
123
views
Can the initial algebra of a 2-variable polynomial functor be computed on the diagonal?
Given a polynomial functor $F$, its initial algebra is denoted by $\mu X.F(X)$.
Now, if $F$ is a 2-variable polynomial functor, $Y \mapsto \mu X.F(X,Y)$ turns out to be functorial and we can, again, (...
- 199
1
vote
0
answers
29
views
On the three different versions of “Liveness with (0, 1, ∞)-Counter Abstraction”
Springerlink and Researchgate point to very similar (but not identical) versions, whereas Pnueli's Website points to a different one. Which version is the latest, which is most complete? Is Pnueli's ...
- 111
4
votes
0
answers
309
views
How to prove that a language that allows infinite loops is still not Turing-complete?
CPS translations will always use pairs, either explictly or by currying. Though I can't find a reference for that, I'm assuming this is a necessary condition (I'd appreciate a reference if someone has ...
- 377
-4
votes
1
answer
171
views
factoring large numbers
I didn't get a reply to my previous post maybe because my question was too stupid?
I'm asking this forum for help in understanding how far we are from factoring very large semiprimes
I'll try to ...
1
vote
1
answer
148
views
Which are the rules for minimal logic in both sequent calculus and natural deduction styles?
Are there any references I could use which explictly contain the rules for minimal logic, both as a sequent calculus and in natural deduction? (Doesn't need to be the same reference for both!)
To give ...
- 377
3
votes
0
answers
76
views
Is there an algorithm for reducing the average row width of a sparse matrix?
Suppose I have a sparse $M \times N$ matrix $A$ and I define the "width" of each row $i$ to be:
$$w_i \equiv r(A_i) - l(A_i),$$
where $r(A_i)$ is the index of the rightmost nonzero element ...
- 131
3
votes
0
answers
60
views
How does extended resolution p-simulate extended Frege?
I found a slide stating that "extended resolution and extended Frege p-simulate each other", without providing a proof. It's obvious that extended Frege p-simulates extended resolution, but ...
- 145
0
votes
0
answers
97
views
When the tree-like resolution size is the same with general(regular) resolution size？
Background:
For an unsatisfiable SAT formulas, the length of a resolution refutaion means the number of clauses in it.
It's well known that there exist exponential separation between tree-like and ...
- 315
2
votes
0
answers
54
views
Intermediate problems between $CC^0$ and $ACC^0$
Definitions
$CC^0[m]$ is the set of languages decidable by constant-depth polynomial-size circuits consisting only of unbounded-fanin $MOD_m$ gates. We write $CC^0$ to mean the union over all $m$. $...
- 1,204
3
votes
0
answers
91
views
Reference Request: Circuit Complexity Theory Course
I want to learn circuit complexity theory. I have found this book "Introduction to Circuit Complexity
A Uniform Approach" by Heribert Vollmer. I have also found lecture notes of one course
...
- 288
1
vote
0
answers
66
views
Finding a Hamiltonian cycle in a graph if we are guaranteed that there are not many of them in the graph
Problem: Given an undirected simple graph $G=(V,E)$ on $n$ vertices, such that there are not more than $c^n$ ($c<2$) Hamiltonian cycles in $G$, find a Hamiltonian Cycle in $G$ if there exists one.
...
- 11
4
votes
0
answers
114
views
Reference for "A Turing machine cannot be equipped with an oracle for itself"
Starting with a basic Turing machine, successive applications of the Turing jump produce successively more powerful machines, that can be indexed by any ordinal. A tempting error for students, and one ...
- 807
0
votes
0
answers
35
views
Let $C$ be collection of subsets of $[N]$. Given, $n\in [N]$, what's the terminology for $card\{s\subseteq [N]\mid n\not \in s,\, s \cup\{n\}\in C\}$?
Let $N \ge 1$ be an integer and let $\mathfrak S$ be a nonempty collection of subsets of $[N] := \{1,2,\ldots,N\}$. For any $n \in [N]$, define $\partial_n \mathfrak S := \{S\setminus\{n\} \mid S \in \...
- 291
0
votes
0
answers
45
views
What Data Structure storing points in space for fast lookup of stored points "near" a query point?
In NLP a common problem is that you have vector embeddings of large vocabularies, and you do manipulations on these vector embeddings to compute some result vector, and then you want to find which ...
- 101
2
votes
1
answer
211
views
Examples for Real-time vs Linear time
A real-time Turing machine (with multiple tapes) runs in linear time. It is known [1] that there are languages recognizable in linear time by a multitape Turing machine but not recognizable in real-...
- 303
4
votes
2
answers
193
views
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
My question is the directed version of this one. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback ...
- 421
2
votes
0
answers
66
views
Submodular function minimization over integer lattice
Let $[k]=\{0,1,\ldots,k-1\}$.
A function $f:[k]^n\to \mathbb{R}$ is submodular if $f(x)+f(y)\geq f(\max(x,y))+f(\min(x,y))$ for all $x,y\in [k]^n$. Here $\max$ and $\min$ are applied coordinate-wise.
...
- 4,367
2
votes
1
answer
115
views
Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time
For a proof, I need the fact that we can efficiently embed an input planar graph into a representative of a specific family of high-treewidth graphs. Specifically, I need an embedding as a topological ...
- 8,896
9
votes
2
answers
265
views
Defining regular language classes with disjoint union
Regular languages are typically defined using the operations of union, concatenation, and Kleene star. Likewise, there are restricted classes of regular languages defined via similar operations, for ...
- 8,896
4
votes
0
answers
43
views
Error analysis of Estrin's method
Estrin's Method is an alternative to Horner's method for evaluating polynomials. To evaluate a polynomial $P(x)=\sum_{i=0}^7 a_i x^i$ at a point $x\in\mathbb R$, it first computes the powers $x^2$ and ...
- 958
6
votes
1
answer
276
views
Relationship between the transition monoid of an automaton and its adjacency matrix
Let $A=(Q,\Sigma, \Delta, q_0, F)$ be an NFA over an alphabet $\Sigma$, $M(A)$ be its transition monoid.
For all $a\in\Sigma$, let $S_a\in\mathbb{B}^{|Q|\times|Q|}$ be the adjacency matrix of $A$ ...
- 1,588
23
votes
0
answers
427
views
Can we do integer addition in linear time?
Why, yes, of course. But I'm actually interested in the cost of computing the sum of multiple integers:
Input: A sequence of nonnegative integers $\langle X_i:i<k\rangle$ written in binary.
Output: ...
- 16.9k