# Questions tagged [reference-request]

Reference-request is used when the author needs to know about work related to the question.

1,603 questions
Filter by
Sorted by
Tagged with
77 views

### Proof for Upper Bound on the Size of the Sum of Rational Numbers

In , 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 ...
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 ...
1k views

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
36 views

### First-order linear mu-calculus?

There is linear $\mu$-calculus (see e.g. ) and first-order $\mu$-calculus (see e.g. here). Has anybody studied first-order linear $\mu$-calculus? : Christian Dax, Martin Hofmann, Martin Lange: A ...
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$ (...
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 ...
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 ...
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 \...
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 ...
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 ...
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 ...
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 ...
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*}...
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 ...
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 ...
342 views

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, (...
1 vote
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 ...
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 ...
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
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 ...
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 ...
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 ...
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 ...
54 views

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 ...
211 views

### Examples for Real-time vs Linear time

A real-time Turing machine (with multiple tapes) runs in linear time. It is known  that there are languages recognizable in linear time by a multitape Turing machine but not recognizable in real-...
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 ...
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. ...
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 ...
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 ...
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 ...
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$ ...
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: ...