All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
63 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
0 answers
41 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
-1 votes
0 answers
44 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
50 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
63 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
43 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
27 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
0 answers
32 views

all k-Vertex Covers

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 acheive ...
Sugyani's user avatar
  • 11
1 vote
0 answers
133 views

3-clauses from the 3CNF when sufficiently large, has already less than $\epsilon$ fraction of satisfying assignments

I have been struggling to understand this answer, but in this answer in proof section I don't understand this line ""there must exist a large enough family of 3-clauses from the 3CNF, in ...
S. M.'s user avatar
  • 127
-3 votes
0 answers
83 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
3 votes
1 answer
177 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
63 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
31 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
2 votes
0 answers
51 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
  • 81
9 votes
1 answer
558 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 admits polynomial-time solvable on trees. It is NP-complete when restricted to the graphs of treewidth 2. The problem can be encoded ...
Prafullkumar Tale's user avatar
4 votes
0 answers
39 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
44 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
59 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
2 votes
0 answers
105 views

Extended Resolution refutation for the clique-coloring formulas

Recall Clique-coloring formulas express that a graph can contain an $m$-clique (complete subgraph $K_m$) and at the same time be colorable in $(m − 1)$ colors: Consider $n$-vertex graph encoded by ...
Brett's user avatar
  • 53
-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
1 vote
0 answers
32 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
44 views

Hardwiring advice (bit string) into Turing machine

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
193 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
54 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
0 votes
2 answers
252 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
87 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
48 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
162 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
88 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
77 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
123 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
146 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
  • 53
5 votes
1 answer
125 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
67 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
238 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
3 votes
3 answers
213 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
57 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
0 votes
0 answers
70 views

Complexity of an algorithm involving permutations

I'm looking to figure out the computational complexity of an algorithm in an application I've written. The application computes the answer to a problem that is $\#P$-hard, and the algorithm I'm asking ...
Matt Samuel's user avatar
1 vote
0 answers
26 views

How can one find a r-division of a graph with strongly sublinear separation profile (separable graphs)?

Thanks for reading, let me provide the definitions first. A separator of a graph $G$ is a set of vertices $C$ such that removing $C$ cuts the graph into two disconnected parts $A, B$ such that they ...
SZH's user avatar
  • 11
2 votes
0 answers
68 views

On The Complexity of Block-Interchange Distance for Binary Strings

The block-interchange distance problem is defined as finding the minimal number of subsequences swaps to apply to an input string to turn it into a desired string. It is a well studied tractable ...
Daniel García's user avatar
4 votes
0 answers
83 views

Working out the constants and probabilities of Stockmeyer's approximate counting algorithm

Stockmeyer's 1983 result on approximate counting using a randomness states that if we have some SAT instance $x$ with $C(x)$ satisfying assignments, then we can find the minimum set of $m$ hash ...
Germ's user avatar
  • 171
-1 votes
1 answer
180 views

Calculation on Sparsification and critical clauses in SAT

I followed from this question. I need to prove, the final result $s_k \leq (1 − \Omega(k^{−1}))s_{\infty}.$ But before prove the final result first I need to prove the $s_k \leq (1 − d/k))s_{\infty}$. ...
S. M.'s user avatar
  • 127
6 votes
1 answer
287 views

Is sorting NP-complete?

SORTING problem. Input: A poset which corresponds to a partially sorted list of different numbers. Output: Number of pairwise comparisons needed (in the worst case) to get a completely sorted array. ...
domotorp's user avatar
  • 13.8k
-2 votes
0 answers
52 views

What is the complexity class of this problem?

What is the complexity class of finding $\# SAT\bmod q$ when $q$ is a prime or prime power and $-\log q\leq \# SAT\bmod q\leq\log q$ holds? Is it $FewP$?
Turbo's user avatar
  • 12.8k
4 votes
1 answer
188 views

Is Optimal Swap Sorting NP-Hard?

Given an array of integers with duplicates, find the minimum number of swaps to sort the array. According to this question, the problem is NP-Complete but the reference given proves NP-Completeness ...
Daniel García's user avatar
-3 votes
0 answers
50 views

Im a graduat student in Medical Informatics

First question: reach is difficult for REACHPROBLEMS. The class REACHPROBLEMS = {1-reach, 2-reach, 3-reach, … }. Prove that: distance = {code(𝐺, 𝑠, 𝑡, 𝑘) ∣ there is a path from 𝑠 to 𝑡 in 𝐺 of ...
system Builder's user avatar

15 30 50 per page
1
2 3 4 5
257