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 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 ...
Arcade_TryHard's user avatar
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 ...
Johan Thiborg-Ericson's user avatar
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\...
Junqiang Peng's user avatar
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 ...
meeeeee's user avatar
  • 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 ...
Soha's user avatar
  • 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 $...
Samdney's user avatar
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 ...
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
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$ (...
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
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 ...
Anton Ehrmanntraut's user avatar
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 \...
Erel Segal-Halevi's user avatar
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 ...
Soha's user avatar
  • 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 ...
Jxb's user avatar
  • 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 ...
Evan Aad's user avatar
  • 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 ...
Nicola Gigante's user avatar
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*}...
sd234's user avatar
  • 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 ...
LiminalSpace's user avatar
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 ...
Per Alexandersson's user avatar
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{...
Thomas Ahle's user avatar
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 ...
EGME's user avatar
  • 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. ...
user3483902's user avatar
  • 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 ...
Soha's user avatar
  • 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 ...
Amor Rei's user avatar
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 ...
FxMySz's user avatar
  • 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, ...
Nicola Gigante's user avatar
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 ...
Blanco's user avatar
  • 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 \...
holf's user avatar
  • 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, (...
sparusaurata's user avatar
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 ...
AlMa0's user avatar
  • 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 ...
paulotorrens's user avatar
-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 ...
user68942's user avatar
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 ...
paulotorrens's user avatar
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 ...
Germ's user avatar
  • 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 ...
Soha's user avatar
  • 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 ...
Jxb's user avatar
  • 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$. $...
Jake's user avatar
  • 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 ...
Soham Chatterjee's user avatar
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. ...
jamal_asif's user avatar
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 ...
Alex Meiburg's user avatar
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 \...
dohmatob's user avatar
  • 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 ...
John_Krampf's user avatar
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-...
QMath's user avatar
  • 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 ...
Blanco's user avatar
  • 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. ...
Chao Xu's user avatar
  • 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 ...
a3nm's user avatar
  • 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 ...
a3nm's user avatar
  • 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 ...
Thomas Ahle's user avatar
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$ ...
Nicola Gigante's user avatar
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: ...
Emil Jeřábek's user avatar

1
2 3 4 5
33