Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,603
questions
23
votes
4
answers
1k
views
Survey on #P and/or counting problems
Can anyone suggest a good and recent survey on counting problems and/or problems that are #P.
- 36.9k
2
votes
0
answers
57
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
votes
0
answers
82
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 ...
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\...
- 3,416
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 ...
- 10.3k
102
votes
41
answers
15k
views
What are the recent TCS books whose drafts are available online?
Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online.
For instance, the Approximation Algorithms entry of the above post cites ...
- 4,451
4
votes
2
answers
523
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 ...
- 16.9k
0
votes
1
answer
125
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 ...
- 16.9k
-1
votes
1
answer
75
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,276
16
votes
3
answers
1k
views
Is the 3-sphere recognition problem NP-complete?
It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere
is in NP, via work by
Saul Schleimer in 2004: "Sphere recognition lies in NP"
arXiv:math/0407047v1 [math.GT].
...
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
6
votes
0
answers
274
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,078
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 ...
- 2,733
29
votes
4
answers
1k
views
Compendium of the Best Approximation and Hardness Results for NP optimization problems
Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result?
Based on the feedback, it seems that it is safe to assume there is not such a ...
- 8,896
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
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 ...
- 16.9k
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 ...
- 216
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*}...
- 226
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
3
votes
1
answer
166
views
Compressing grammars by introducing ambiguity and left-recursion
This is a reference request. What is known about the following questions?
Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a
new grammar $G'$ which also ...
- 5,840
6
votes
3
answers
334
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 ...
- 11.3k
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 ...
- 325
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
14
votes
2
answers
1k
views
Space alternating hierarchy
It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions).
In the same paper, Immerman state that the ...
- 105
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{...
- 4,681
6
votes
2
answers
610
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 ...
- 16.9k
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
72
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 ...
- 177
16
votes
1
answer
359
views
Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?
I hope that mathematical logic / recursion theory type questions are welcome here. I am sorry this question is so long and technical, but I believe that if you read it you will find that it is well-...
- 648
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
371
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 ...
- 5,840
10
votes
3
answers
488
views
Complexity results for Lower-Elementary Recursive Functions?
Intrigued by Chris Pressey's interesting question on elementary-recursive functions, I was exploring more and unable to find an answer to this question on the web.
The elementary recursive functions ...
- 16.9k
0
votes
0
answers
76
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, ...
- 16.9k
1
vote
0
answers
159
views
Can we describe any context-sensitive language by a grammar without left recursion?
The main question: is it possible to avoid left recursion in a context-sensitive grammar (see example below), i.e., if for any context-sensitive language $L$, there exists some context-sensitive ...
- 83
1
vote
1
answer
88
views
Code indistinguishability assumption for Code based cryptography (in special cases)
Cryptosystems that are based on error correcting codes are often based with hardness of the two problem.
Computational syndrome decoding is hard
Indistinguishability Assumption (IA): Distinguishing ...
- 83
8
votes
0
answers
171
views
Can one find good distance-2-separators in planar graphs?
It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph.
However, it ...
- 83
7
votes
2
answers
338
views
Efficiently ordering typed programs
Sometimes it is useful to enumerate in increasing order
programs that have a given type. A
simple example is test
generation for compilers: we want to test a new optimising phase and
are ...
- 11.4k
1
vote
2
answers
96
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 ...
- 1,767
23
votes
0
answers
433
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
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
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
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 ...
CommunityBot
- 1
7
votes
2
answers
2k
views
Test set and benchmarks for linear programming
I am searching for test instances and benchmarks for linear programming, in particular, when solved by a simplex method and implemented with floating-point arithmetic.
This includes test suites, to ...
- 111
-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 ...
- 11
9
votes
3
answers
327
views
Resumption-based IO systems?
I've been playing around with resumptions lately, mostly from Abramsky's classic paper Retracing Some Paths in Process Algebra. They are quite slick (basically solutions to the domain equation $R = I \...
9
votes
2
answers
920
views
Is this a known combinatorial optimization/scheduling problem?
We are given $n$ stacks which hold "items" of different colour and a machine that can process multiple items of the same colour in one go. At each step, we can remove one item from the top of each ...
CommunityBot
- 1
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 ...
- 307
4
votes
2
answers
214
views
How exactly does a compatible reduction relation change the $\pi$-calculus?
The reduction relation given for the $\pi$-caculus is usually not compatible (i.e., it's not preserved under arbitrary contexts). Quoting Milner's The Polyadic $\pi$-Calculus: A Tutorial:
It is ...
- 11.4k