All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
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$ ...
user11718766's user avatar
0 votes
0 answers
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 ...
Demi's user avatar
  • 518
0 votes
0 answers
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 ...
pyridoxal_trigeminus's user avatar
1 vote
0 answers
64 views

Abstract domain monad

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: ...
Alecs's user avatar
  • 11
5 votes
0 answers
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.
domotorp's user avatar
  • 13.8k
0 votes
0 answers
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 ...
Petroleum Engineer's user avatar
4 votes
0 answers
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 ...
orlp's user avatar
  • 885
0 votes
1 answer
35 views

Question about claw-free graphs

Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ? There are three induced paths through $u$: between $y$ and $z$ (i.e., $y \...
BBK's user avatar
  • 103
1 vote
1 answer
42 views

Sequential Two-player Game related to "Bandit Detection"

Alice and Bob play a game over $n$ rounds. At each round, Alice picks a number $x_t \in [0,1]$ and Bob simultaneously chooses whether to "peek" at the number $x_t$ which is represented by a ...
Amaryllis 's user avatar
-1 votes
1 answer
69 views

The role of Turing machines in computational complexity

In the popular book "Introduction to algorithms" by CLRS even though rigorous proofs are given about the complexity analysis of algorithms there is no mention of Turing machines. Instead ...
Sanyo Mn's user avatar
2 votes
0 answers
56 views

Distance between Fourier distributions of independent random Boolean functions

For a boolean function $f: \{-1,+1\}^n \to \{-1,+1\}$, the squared Fourier coefficients $\{\hat{f}(S)^2\}_{S \subseteq \{0,1\}^n}$ form a probability distribution. I want to know what the total ...
helloworld's user avatar
2 votes
0 answers
164 views

Can an $n$-element subset of a $2n$-element set be stored in $2n - \omega(1)$ bits?

There are $\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \cdot (1 - o(1))$ possible $n$-element subsets of a $2n$-element set. Therefore, any data structure storing such a set must use at least $2n - O(\...
templatetypedef's user avatar
1 vote
1 answer
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, ...
FooFighter39's user avatar
-2 votes
0 answers
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 ...
RIM's user avatar
  • 1
2 votes
0 answers
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 ...
pyridoxal_trigeminus's user avatar
2 votes
0 answers
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 ...
Julian G.'s user avatar
0 votes
0 answers
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 ...
user72110's user avatar
0 votes
0 answers
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 ...
TheoryQuest1's user avatar
1 vote
1 answer
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 ...
Sugyani's user avatar
  • 13
-3 votes
0 answers
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 ...
XL _At_Here_There's user avatar
4 votes
2 answers
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 ...
wonderinghuh's user avatar
4 votes
0 answers
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 ...
Mingda Qiao's user avatar
1 vote
0 answers
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 ...
fanda's user avatar
  • 11
3 votes
0 answers
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 ...
Tejas's user avatar
  • 91
12 votes
2 answers
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 ...
Prafullkumar Tale's user avatar
4 votes
0 answers
44 views

Complexity of solving random underdetermined polynomial equations over finite fields

Consider a random system of degree-$d$ polynomials, with $n$ variables and $m$ equations, over some finite field $\mathbb{F}_q:$ $$\begin{align}\sum_{\substack{(\alpha_1,\dots,\alpha_n) \in \mathbb{Z}...
Quang Dao's user avatar
3 votes
0 answers
54 views

Hardness of Approximation for Three Matroid Intersection

I am searching for the best known hardness of approximation bound for three matroid intersection. The input is three matroids on the same ground set which are accessible using three different ...
MatroMan's user avatar
0 votes
0 answers
66 views

Is there a Hidden subgroup problem in BQP but suspected not to be in NP?

Wikipedia lists HSP problems in abelian and non-abelian groups. So does the following (extensive) compedium. I searched and found none is a BQP-complete (or even BQP-hard) problem. There has been a ...
Manish Kumar's user avatar
3 votes
0 answers
41 views

Affine point matching in general dimensions

Fix a positive integer $d$ and consider the $d$-dimensional Euclidean space $\mathbb{R}^d$. Let $S$ and $T$ finite subsets of $\mathbb{R}^d$ of the same size $n$. Under the assumption that $S$ and $T$ ...
rr314's user avatar
  • 131
-1 votes
0 answers
57 views

Communication complexity of median of two sets [migrated]

I am working on exercise 1.6 of the textbook Communication Complexity and Applications by Anup Rao and Amir Yehudayoff. Alice and Bob get sets X and Y in {1,2,...,n} respectively and they want to ...
Ruoyu Meng's user avatar
2 votes
0 answers
35 views

Characterization of CF languages closed under circular shifts

Along the same lines as what was asked in this post: Is there a simple characterization of regular languages closed under circular shifts? Are there simple characterizations/properties of Context Free ...
Marzio De Biasi's user avatar
0 votes
0 answers
46 views

Hardwiring advice (bit string) into Turing machine [closed]

In paper, page 5, 1st paragraph, it is stated that: Notice that an n-state Busy Beaver, if we had it, would serve as an O(n log n)-bit advice string, “unlocking” the answers to the halting problem ...
cartman's user avatar
0 votes
2 answers
203 views

Shortest path with permutations and fixed dimension

I'm thinking of extensions of the shortest path problem which are solvable in polynomial time. One way to do this is to consider the shortest path problem on a weighted directed graph with weights on $...
user1868607's user avatar
1 vote
0 answers
56 views

Is there a succinct representation of factoring which remains computationally intractable?

I'm looking for a succinct version of the factoring problem: i.e. given integers N and k, does N have a prime factor less than k, but somehow the input takes exponentially fewer bits to input? Ideally ...
Hans Schmuber's user avatar
1 vote
2 answers
270 views

Nondeterministic Turing Machines as deciders, versus NP and co-NP

While preparing a class, I stumbled over a point that I could not elucidate. Explaining it requires a few step. Deciding vs Recognizing: A Turing machine $M$ decides a language $L$ if whenever $s\in ...
Arnaud Casteigts's user avatar
0 votes
0 answers
90 views

What algorithms are there for ANN?

I'm a software engineer working on a large project for which one of the subcomponents involves approximately solving the nearest neighbors problem (to a factor of $1+\epsilon$). I was wondering what ...
Jaclyn's user avatar
  • 11
2 votes
0 answers
51 views

Are sequenceable groups self-reducible?

A non-trivial finite group $G$ of order $n$ is said to be sequenceable if its elements can be arranged in a sequence ($g_{1}, g_{2} \dots ,g_{n}$) in such a way that the partial products ($a_{1}, a_{2}...
SUTANAY BHATTACHARJEE's user avatar
2 votes
2 answers
163 views

property of minimal triangulations

A graph is chordal if every cycle on four or more vertices contains a chord i.e. an edge between non-adjacent vertices of the cycle. A triangulation (or chordalization) of a graph $G=(V,E)$ is the ...
CuriousChordalizer's user avatar
0 votes
0 answers
93 views

On the polynomial-size Frege proof of the propositional pigeonhole principle

I'm reading a lecture note on the proof of PHP, which mentioned that a "basic fact" $$ \left(\sum\limits_{i=1}^{s-1} A_i\ge a\right) \land A_s \to \sum\limits_{i=1}^s A_i\ge a $$ is ...
Soha's user avatar
  • 187
2 votes
0 answers
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 ...
StubbornSnail's user avatar
2 votes
0 answers
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 ...
user72031's user avatar
0 votes
0 answers
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 ...
Dominic van der Zypen's user avatar
3 votes
1 answer
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 ...
Brett's user avatar
  • 33
5 votes
1 answer
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 ...
user1868607's user avatar
1 vote
0 answers
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 ...
Eleonora's user avatar
5 votes
1 answer
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, ...
Mengfan Ma's user avatar
4 votes
3 answers
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 ...
Erel Segal-Halevi's user avatar
-1 votes
0 answers
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,...
FishyK's user avatar
  • 1
1 vote
0 answers
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 ...
Russell Easterly's user avatar
0 votes
0 answers
58 views

Undecidability of games with limited hidden state

Surprisingly, approximate win probability for one-player games with randomness and 3 bits of hidden state (in addition to non-hidden state; rational transition probabilities) is uncomputable. Question:...
Dmytro Taranovsky's user avatar

15 30 50 per page
1
2 3 4 5
257