# All Questions

12,819 questions
Filter by
Sorted by
Tagged with
3 views

### Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned: Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ ...
• 101
39 views

### Why does the Time Hierarchy Theorem fail relative to promise problems?

Define Program Evaluation (PE) to be the promise problem of determining whether a program (written in a Turing-complete language) returns True or False. The promise is that the program will return ...
• 518
18 views

### Detection of intersection between two $d$-dimensional convex polytopes with at most $N$ facets

I am looking for a reference on the current state-of-the-art algorithm(s) for detecting intersection between two $d$-dimensional convex polytopes, with time complexity depending on their number of ...
1 vote
64 views

I was reading old lecture from a CS course at Cornel and I have some doubts about the following at 2.4 It defines how to transform domains between each other via a Galois Insertion, more formally: ...
• 11
147 views

### Is GCT still active?

Is Mulmuley's geometric complexity theory program still active? I tried to look it up online, and I haven't seen anything from the last couple of years.
• 13.8k
34 views

### How to estimate slope of a feature in image?

I am working on analyzing data obtained from acoustic sensors. During analysis of acoustic data, I got frequency-wavenumber spectrum of acoustic data as shown below. I am looking for a technique that ...
46 views

### Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort for sorting array $a$ of size $n$. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how ...
• 885
35 views

• 2,141
1 vote
165 views

### Research masters programs in theoretical computer science (with a focus on complexity theory)

I am in my 2nd year of my Computer Science degree. I am deeply interested in Complexity Theory, and I plan to pursue a career in this field I am from South Asia, and research here is not up to par, ...
57 views

### reduction from $permanent _{-1,0,1}$ to $permanent _{0,1,2,3,\dots,n}$

i want to prove the reduction from $\#permanent _{-1,0,1}$ to $\#permanent _{0,1,2,3,\dots,n}$ anhere what i do :ok for the first reduction here what i do : Let (A) be an (n \times n) matrix with ...
• 1
69 views

### References for algorithms to compute approximating polytopes for arbitrary convex sets

There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes. One of the main results in this area is that under some mild ...
89 views

### Monads whose Kleisli arrows can be "applicativized"

Has anyone thought about what constraints a monad should satisfy in order for its arrows to be able to be "applicativized". That is, for what monads $M$ is it the case that there is an ...
55 views

### Is every 4-claw-free graph a bounded degree graph?

I am looking of some graph properties of 4-claw free graph, where neighborhood of every vertex has independent set of size at most 3. As per my observations, this type of independent set size ...
35 views

### converting K-SAT clause to a p-in-L-SAT equation

Given a generic K-SAT instance $S$ with $n$ boolean variables. Is it possible to convert a clause of this instance into an equivalent p-in-L SAT system of equations such that the number of new clauses ...
• 811
1 vote
102 views

### Enumerating all Vertex Covers of Size at most $k$

I am looking into the problem to generate all possible vertex covers (including both minimal vertex covers and non-minimal vertex covers) of size at most $k$? Is there any algorithm that can achieve ...
• 13
87 views

### The range of Busy Beaver Function is immune set？

I am not familiar with Busy Beaver function ---BB(n). Some body assert that the range of BB(n) is not c.e. set, somebody even say that the range of BB(n) is not c.e. set and it is an immune set. But ...
• 1,064
276 views

### What is the relevance of Real Analysis in TCS?

I'm a recent Math major who switched to a double major with Computer Science. I'm petitioning my CS Department Chair to allow me to take Real Analysis in place of Algorithms. I've already taken Data ...
• 357
72 views

### Uniform lower bounds in terms of the matrix multiplication exponent $\omega$?

Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is ...
1 vote
32 views

### Placing a circle in a point cloud

I need to place a circle with fixed radius in a cloud of points. The circle also must lay in a polygon (the points are also in that polygon) This circle has to contain as many points as possible. Are ...
• 11
60 views

### Hardness of Orthogonal Vectors in the Average-Case

In a result of Ball et al. from 2017 (Average-Case Fine-Grained Hardness), it is shown that if the Orthogonal Vectors Hypothesis (OVH) is true, then there is no algorithm that can compute the ...
• 91
644 views

### Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Do we know any problem that satisfies the following criteria? It is polynomial-time solvable on trees. It is NP-complete when restricted to graphs of treewidth 2. The problem can be encoded only ...
44 views

• 187
35 views

### Homeomorphic subtree extraction in integer sorting time

Background Given a rooted, binary tree $T$ with leaves bijectively labeled by $\{1, \ldots, n\}$ (a "phylogenetic tree"). Let $L \subseteq \{1, \ldots, n\}$, and $|L| = k$. The homeomorphic ...
78 views

### Learning discrete math for research

This might be an unusual question, but please bear with me. As a graduate student in mathematics, I haven't delved deeply into several discrete math subjects relevant to research in theoretical ...
125 views

### Error in TAOCP 4a on the bipartite graph constructed from a hypergraph

The first sentence on page 33 of Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 4a reads: Furthermore, a hypergraph is equivalent to a bipartite graph with vertex set $V \cup E$ and ...
167 views

### Horn clause on cnf

Recall that a CNF formula is Horn if each clause contains at most one positive literal. Is it possible any unsatisfiable Horn CNF formula has a polynomial-size treelike Resolution refutation? Is there ...
• 33
129 views

### Shortest path with affine updates and fixed dimension

One may look at the shortest path problem on a weighted directed graph with weights on $\mathbb{Q}$ as the problem of minimizing a rational value $x$ which is updated at each edge of the graph with ...
• 987
1 vote
69 views

### Are there any candidate languages in NE but not E?

Let ${\bf E}=\text{DTIME}(2^{O(n)})$ and ${\bf NE} = \text{NTIME}(2^{O(n)})$ Is there any candidate natural language being in ${\bf NE} \setminus {\bf E}$, that is, people believe is ${\bf NE}$ but ...
• 11
241 views

### How many numbers are needed such that the possible subset sums cover $\{1, \frac{1}{2}, \frac{1}{3},\dots, \frac{1}{2^m}\}$?

For a multiset $N$ of positive numbers, the set of possible subset sums is $f(N)=\{s\in \mathbb{R}: \exists S\in 2^N, s=\sum_{a\in S} a\}$. We say $N$ generates $T$ if $T\subseteq f(N)$. For example, ...
• 513
240 views

### A Travelling Salesman variant where the next distance depends on distance travelled so far

The travelling salesman problem can be seen as a problem of selecting a permutation on $\{1,\ldots,n\}$ of minimun length, where the length of a permutation $\sigma$ is determined by pairwise ...
• 2,188
35 views

### Lower bound for optimal solution for 3-hitting set approximation problem?

I want to come up with a 3-approximation ratio for the hitting set problem: There exist subsets $F_i$ of $F$ for $i=1,...,k$ of some numbers of universe $U=\{1,...,n\}$ with $∣F_i∣=3$ e.g. \$F_1=\{1,2,...
1 vote
47 views

### Short learned clauses for XSAT

Are there any studies about how effective a limited resolution pre-processor is for DPLL-CDCL type SAT solvers? By limited resolution pre-processor I mean a pre-processor that generates short (1,2, or ...