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
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.
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\...
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 ...
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 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 ...
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 ...
-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 $...
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 ...
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 ...
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 \...
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 ...
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 ...
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 ...
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 ...
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 ...
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*}...
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 ...
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 ...
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 ...
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 ...
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, (...
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 ...
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{...
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 ...
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. ...
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 ...
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-...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 \...
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 ...
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 ...
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 ...
-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 ...
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 ...
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 ...
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 ...

1
2 3 4 5
33