All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
19 views

Higher dimensional automata?

An NFA is just the data of a labelled, directed multigraph with a accepting predicate over the vertices. Simplicial sets generalize directed multigraphs by allowing the existence of higher dimensional ...
Steven Schaefer's user avatar
1 vote
0 answers
19 views

Do prefix hash functions work well for approximate counting?

Given some set $S \subseteq \{0,1\}^n$, suppose we want to approximate $|S|$. One approach is hashing-based approximate counting, which exploits the structure of hash functions to approximately halve $...
Germ's user avatar
  • 181
3 votes
0 answers
51 views

Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?

We know that $\mathsf{BPP}$ is in $\mathsf{\Sigma^P_2\cap \Pi^P_2}$ by Sipser-Lautemann, as this proof relativizes we can get $\mathsf{BPP^{NP} \subseteq \Sigma^P_3\cap \Pi^P_3}$, but are there any ...
Marsh's user avatar
  • 31
0 votes
0 answers
47 views

Proof of coNE ⊆ NE/poly

I'm finding it hard proving that NE/poly contains coNE which is backed by Complexity Zoo. It states that we can use the proof for NEXP/poly containing coNEXP but the link to the reference paper ...
rock_lee's user avatar
1 vote
0 answers
24 views

Is the Maximum Coverage Problem Remains as Hard when Taking Most Sets?

In the maximum coverage problem (also known as max k-cover) we are given a universe $U = \{e_1,\ldots, e_n\}$ of elements, a collection $F = \{S_1,\ldots, S_m\} \subseteq 2^U$ of sets over $U$, and an ...
John's user avatar
  • 385
2 votes
0 answers
27 views

Generalization of the generalization of the evasiveness conjecture

The generalized evasiveness conjecture (Aanderaa, Rosenberg, Karp, Kahn, Saks, Sturtevant) states that any non-constant, monotone ($x\le y \Rightarrow f(x)\le f(y)$, weakly symmetric Boolean function ...
domotorp's user avatar
  • 14k
3 votes
1 answer
51 views

Straight-line program for sets

Let $\mathcal{S}$ be a collection of sets. A set straight-line program that enumerates $\mathcal{S}$ is a sequence of sets $B_1,\ldots,B_m$, such that $\mathcal{S}\subseteq \{B_1,\ldots,B_m\}$. For ...
Chao Xu's user avatar
  • 4,429
0 votes
0 answers
33 views

Induced subgraphs with interface

I am interested in graphs with interfaces, i.e. graphs with distinguished vertices that can be plugged into a larger context. I call "island" of a graph $G$ a subgraph $I$ such that there ...
Denis's user avatar
  • 8,843
-1 votes
0 answers
16 views

Neighborhood in a graph coloring problem

I have a question regarding the neighborhood structure of a graph coloring problem in Julia. So my problem is that I have a list of 250 incompatibilities of courses so as an example I have course 9 ...
Ryan's user avatar
  • 1
4 votes
0 answers
122 views

Question about Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

I have a question about the paper, specifically the proof of the Theorem 2.4(i). It starts by saying Clearly, $P_n(S) \ge P(S) \cdot \Pr(H_1 \cap \ldots \cap H_n = \{ 0^n\})$ Here, $S \subseteq \{0, ...
deltaepsilonnn's user avatar
0 votes
1 answer
156 views

This is a variant of the unsolved problem of $a^6+b^6+c^6≠d^6+e^6+f^6$, for distinct primes. Does it have any significance for Exact Three Cover?

Suppose, I'm solving Exact 3 Cover, given a list with no duplicates $S$ of $3m$ whole numbers and a collection $C$ of subsets of $S$, each containing exactly three elements. The goal is to decide if ...
The T's user avatar
  • 159
0 votes
0 answers
40 views

On a modular inverse graph construction

Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
Turbo's user avatar
  • 12.9k
8 votes
0 answers
117 views

Resources on how to write good TCS papers

I am looking for good resources on how to write papers, which could be useful for graduate students in TCS. The internet seems to be full with style books, papers, and online talks on the subject, but ...
Or Meir's user avatar
  • 5,460
4 votes
1 answer
114 views

How does gcd in $\mathbb Z_p[x]$ and $\mathbb Z_q[x]$ relate to gcd in $\mathbb Z_n[x]$?

I'm trying to understand part of a paper. How does the difference of gcd in $\mathbb Z_p[x]$ and $\mathbb Z_q[x]$ relate to the gcd in $\mathbb Z_n[x]$? And why is the result of gcd in $\mathbb Z_n[x]...
userg93's user avatar
  • 43
2 votes
0 answers
59 views

On mod $p$ constructions related to determinant

Given an $m\times m$ matrix $M\in\mathbb Z^{m\times m}$ and a prime $p$, is it possible to construct in $Logspace$ another matrix $t_1(M)$ whose determinant is guaranteed to be determinant $Det(t_1(M))...
Turbo's user avatar
  • 12.9k
3 votes
0 answers
46 views

Partial Hamiltonian Path Optimization Problem

Let $G = (V,E)$ be a directed graph. Define the optimization problem in which the goal is to find a subset of edges in $G$ of maximum cardinality, such that (i) the in-degree and out-degree of each ...
John's user avatar
  • 385
0 votes
0 answers
71 views

Jukna Boolean Function Complexity Exercises 7.2 & 7.3

The two exercises go like following: 7.2. Show that $STCON_n$ can be computed by a monotone nondeterministic branching program of size $\mathcal{O}(n^2)$. Hint: Take one contact for each potential ...
cubic theorist's user avatar
7 votes
0 answers
59 views

Tree of addition chains

Addition chains are a well-known way of building up a number from 1 by adding two previously computed numbers. It is a long-standing open problem to determine the complexity of computing the length of ...
domotorp's user avatar
  • 14k
0 votes
1 answer
72 views

Hardnnes of Approximation of Minimum Vertex Cover on 3-Regular Graphs

The paper [Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs, Austrin, Khot, Safra] Shows that assuming the Unique Game Conjecture (UGC) the minimum vertex cover problem ...
John's user avatar
  • 385
-1 votes
2 answers
123 views

Help understand why FOL wff are enumerable, but FOL is undecidable

I am very new to this. I am trying to understand some basics about what kinds of enumerations in FOL are possible, and which are not. If you accept that FOL is defined in terms of a finite number of ...
Julius Hamilton's user avatar
3 votes
0 answers
46 views

Hardness of deciding fractional chromatic number at most $k$

I want to find a reference for the following statement. Here, $\chi_f(G)$ denotes the fractional chromatic number of a graph $G$. For every fixed $r>2$, deciding $\chi_f(G) \leq r$ for a given ...
Minsoo Kim's user avatar
-6 votes
0 answers
25 views

Harassment . . how do i de-lint/ rust a human body

Perl/gitkraken/py caffe/neural networks I have an issue with harassment via Remote aerial can someone tell me a solve.??? what's the most simple technique to getting unwanted 2/3d matrices(namely ...
Angus John Murray's user avatar
0 votes
0 answers
27 views

Variants of weak optimization problems for convex sets

In their famous book, Grotschel Lovasz and Schrijver (1993) present several algorithmic problems on convex sets. Each of these problems has a strong variant and a weak variant. In particular, the ...
Erel Segal-Halevi's user avatar
3 votes
0 answers
58 views

Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

I have 2 type of decision problems: either in $\mathsf{BPP}$ or in $\mathsf{NP}$; and I want to decide fixed Boolean combinations of them. Since $\mathsf{BPP}$ is closed under Boolean combinations and ...
DiegoEmilio's user avatar
0 votes
0 answers
67 views

Is every non recurvisely enumerable language is RE-hard? [closed]

Is every language $L \notin RE$ is $RE$-hard? Similarly, is every language $L \notin RE \cup coRE$ is $RE$-hard and $coRE$-hard? It seems like a simple question but I can't find an answer. I tried to ...
Amit Keinan's user avatar
0 votes
0 answers
52 views

Why can't we just reduce from Bounded HALT to Bounded PCP?

We know that: PCP is famously undecidable (as it can encode any DTM), but Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and Bounded-PCP (there is a matching ...
apirogov's user avatar
  • 101
3 votes
1 answer
200 views

How to encode a function from an existential type

I am having trouble using parametricity to show that existential types work in System F (or System Fω) in the way one would expect them to work. It is known that an existential type $\exists t.~P~t$ (...
winitzki's user avatar
  • 389
-3 votes
0 answers
55 views

Is there a generalized SAT problem for many-valued logics?

Is there a generalized SAT problem for many-valued logics? related: "Is there a generalized SAT problem for higher-order logics?"
Geremia's user avatar
  • 105
-2 votes
0 answers
52 views

Graph theoretic problems complete for certain counting classes

What are some graph theoretic problems complete for SpanL, TotL, OptL classes? SpanP, TotP, OptP classes?
Turbo's user avatar
  • 12.9k
-1 votes
0 answers
53 views

NTM preserving modular number of accepting paths

Given a prime $p$ and an NTM with number of accepting paths $g$, is it possible to construct an NTM with number of accepting paths $g\bmod p$ in polynomial time where by $g\bmod p$ I mean the ...
Turbo's user avatar
  • 12.9k
0 votes
1 answer
90 views

Is there a generalized SAT problem for higher-order logics?

The SAT problem is based upon Boolean expressions, but is there a generalized SAT problem based upon higher order logics?
Geremia's user avatar
  • 105
0 votes
0 answers
25 views

Recognizeability of PFTM

I encountered this problem here: https://theory.stanford.edu/~trevisan/cs172/ps05.pdf Consider the language $$PFTM := \{\langle M \rangle : \text{$M$ is a Turing machine and $L(M)$ is prefix free} \}$$...
redrobinyum's user avatar
7 votes
1 answer
297 views

Comparing Shor's and Regev's Quantum Factoring algorithm

Regev's factoring algorithm works as follows: (Say, for factoring integer $N$; input bitsize $n$). Step I: Choose $a_1,\ ..., a_d$ small number (say, squares of first $d$ primes: (4, 9, 16, ...), ...
108_mk's user avatar
  • 225
0 votes
0 answers
46 views

cutting plane method for convex optimization

The cutting plane approach in convex optimization is a general recipe for minimizing a convex function. The argument relies on the fact that using the gradient vector, we can cut the feasible set into ...
MMH's user avatar
  • 101
1 vote
0 answers
151 views

Relation between $k$-sum failure and $P=NP$

If $P=NP$ then $W[1]=FPT$ holds. Hence $k$-sum conjecture fails at a finite $k$. What can we say about the time complexity of $SAT$ and the lowest $k$ at which $k$-sum conjecture fails? In particular, ...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
70 views

Separating disjoint PSPACE-hard sets by NP-separators (and some variants)

I am trying to find some references or arguments for results of the form, where $X,Y$ vary over complexity classes, typically with $X\subseteq Y$, and $A,B$ are disjoint languages that are $Y$-hard: ...
Anupam Das's user avatar
5 votes
0 answers
70 views

Hardness of Computing Tribes-DNF by Decision Trees

In this paper on "The Polynomial Hierarchy, Random Oracles, and Boolean Circuits", Fact (3.2) states that it is impossible for a polylogarithmic depth decision tree to compute the Tribes-DNF ...
CHLander's user avatar
8 votes
1 answer
303 views

In logic programming, what would a language with second-order model theory gain?

HiLog is described as a logic programming language with higher-order syntax, but first-order model theory. For example, it allows you to define a map over lists: ...
MWB's user avatar
  • 259
3 votes
1 answer
79 views

Testing if a distribution over $\mathbb{F}_2^n$ is heavily supported on a subspace

Let $P$ be a distribution over n-bitstrings which we will view as elements of $\mathbb{F}_2^n$. Given sample access to $P$, I am looking for an algorithm that tests if $P$ is heavily concentrated on a ...
Marsl's user avatar
  • 131
1 vote
0 answers
64 views

Perceptual similarity problem in theoretical computer science

A perceptual hash is a type of locality-sensitive hash, which is analogous if the features of the images are similar. Let $I$ denote the set of images and $y_1 \approx y_2 $ means images are similar (...
David's user avatar
  • 123
1 vote
0 answers
40 views

Practical Applications of Information Algebras

I've started reading Information Algebras, Kohlas (the Wikipedia may give you the gist) and I am curious as to whether any ideas from this theory/book could be practically implemented, perhaps as some ...
Matt X's user avatar
  • 111
4 votes
0 answers
130 views

Learning a regular language with a specified closure property

Consider an alphabet $\Sigma$, and a partial transformation function $f:S\to\Sigma^\ast$ defined on some subset $S\subseteq\Sigma^\ast$. Let $S_f$ denote the set of strings $s\in S$ such that $f^n(s)\...
LegionMammal978's user avatar
5 votes
0 answers
87 views

Does there exist a cryptographic associative hash function?

Does there exist a function $f(x,y)$ with these properties: Computing $f(x,y)$ is in P. $f$ is associative: $f(x, f(y, z)) = f(f(x, y), z)$. $f$ is one-way (assuming P $\neq$ NP): Given the value ...
Dale's user avatar
  • 251
-2 votes
0 answers
35 views

NP vs QuasiP and W[1] vs FPT

If $F[1]=WPT$ then ETH is false. The converse is unknown (https://en.wikipedia.org/wiki/Exponential_time_hypothesis#Structural_complexity). How about the strong assumption of $NP\subseteq QuasiP$? ...
Turbo's user avatar
  • 12.9k
10 votes
2 answers
619 views

Complexity of NFA cofiniteness

What is the complexity, given as input an NFA, of determining if it is cofinite (i.e., the complement of its language is finite)? Surely this must be known but I can't find a reference. Note that the ...
M.Monet's user avatar
  • 1,429
0 votes
0 answers
43 views

For which k can we decide whether an input k-gon tiles?

Can we decide whether a given polygon can tile the whole plane? First, let me briefly summarize what is known about this problem. If we only allow translations, then the problem is always decidable in ...
domotorp's user avatar
  • 14k
0 votes
0 answers
56 views

Complexity of LSB and MSB of Diffie-Hellman

Given generator $g$ of multiplicative cyclic group modulo $p$ a prime and two elements $h_1$ and $h_2$ such that there are $x_1$ and $x_2$ respectively satisfying $g^{x_i}=h_i\bmod p$ at every $i\in\{...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
64 views

Why is the model-checking problem for MSO $\textsf{PSPACE}$-complete?

I am currently reading "Parameterized Complexity Theory" by J. Flum and M. Grohe. In Chapter 10.3 they state in the first paragraph: Let us remind the reader that the model-checking problem ...
user11718766's user avatar
1 vote
0 answers
61 views

Is there any augmenting graph algorithm available for finding maximum independent set problem in K1,4-free graph in polynomial time

$K_{1,4}$-free graph is the graph with no induced subgraph of the form $K_{1,4}$ An augmenting graph $H$ for $S$ (which is an independent set) is an induced bipartite subgraph of $G$, where $H = (B, ...
user72110's user avatar
0 votes
0 answers
65 views

Reductions That Acts on Witnesses

We say that a language $X$ is polynomial time reducible to $Y$, intuitively, if given an algorithm for solving $Y$, there's an algorithm for solving $X$. I know this can be formalized using Karp ...
Boran Erol's user avatar

15 30 50 per page
1
2 3 4 5
258