All Questions

Filter by
Sorted by
Tagged with
0 votes
1 answer
44 views

Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?

Suppose I have a linear program $LP1=\{\mbox{Maximize }c^\top x \mid x\in \mathcal{P}\}$ for some polytope $\mathcal{P}\subseteq [0,1]^n$, which is known to have fractional extreme points. Suppose ...
gov's user avatar
  • 341
0 votes
0 answers
38 views

Bipartite Matching with a Partition Constraint over the Vertices

Let $G = (X,Y,E)$ be a bipartite graph and let $X_1,\ldots,X_r$ be a partition of $X$. For some $i \in \{1,\ldots, r\}$ and $E' \subseteq E$ we say that constraint $X_i$ is covered by some $E'$ if ...
John's user avatar
  • 412
0 votes
0 answers
70 views

What work on min max connectivity problems has there been?

For instance has min max spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c_{v,e}$ of each resource $i$. And we wish to find a spanning tree minimizing the maximum ...
Hao S's user avatar
  • 228
0 votes
1 answer
28 views

How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?

I am working on a problem where I have $n $ workers, each with a cache that already contains a specific set of objects. Additionally, I receive $n \times m$ sets of objects. My task is to assign ...
Han Tian's user avatar
3 votes
1 answer
169 views

Polynomial Identity Testing for $\prod \sum \prod$

I am reading a survey on polynomial identity testing by Saxena. On page 6 he writes that PIT for depth-3 circuits of the form $\prod \sum \prod$ is trivial. He gives no citation and as such I believe ...
Anakin Dey's user avatar
2 votes
1 answer
34 views

Find the weighted perfect "1-to-k" matching algorithm with minimum aggregated k max weight

Similar with Weighted matching algorithm for minimizing max weight. Consider the following matching problem: Input: a complete weighted bipartite graph with $n+(k*n)$ vertices, given by $n$, $k*n$, ...
Han Tian's user avatar
0 votes
0 answers
65 views

Has multiobjective prize collecting steiner tree or TSP been studied?

Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes to the root that maximizes the minimum amount of any resource using ...
Hao S's user avatar
  • 228
4 votes
0 answers
102 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
2 votes
0 answers
56 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
  • 191
4 votes
0 answers
94 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
  • 41
0 votes
0 answers
83 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
56 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
  • 412
6 votes
0 answers
123 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
4 votes
1 answer
117 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,479
1 vote
0 answers
94 views

Induced subgraphs with interface

I am interested in hypergraphs with interfaces, I'll call them simply "graphs" in the following. Formally, a graph of sort $k$ is a tuple $(V,E,i)$ with $E\subseteq V^+$ is the set of edges, ...
Denis's user avatar
  • 8,903
11 votes
1 answer
371 views

Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

I have a question about the paper "NP is as easy as detecting unique solutions" by Valiant and Vazirani, specifically the proof of the Theorem 2.4(i). The proof starts by saying Clearly, $...
deltaepsilonnn's user avatar
0 votes
1 answer
175 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
47 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
  • 13k
9 votes
0 answers
157 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,615
4 votes
1 answer
136 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
68 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
  • 13k
3 votes
0 answers
52 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
  • 412
7 votes
0 answers
68 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
112 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
  • 412
-1 votes
2 answers
149 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
53 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
0 votes
0 answers
29 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
64 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
2 votes
0 answers
87 views

Evidence for $\oplus P\subseteq\#P$ and barriers to proving it

Is there evidence that $\oplus P\subseteq\#P$ and evidence towards $\oplus P\not\subseteq\#P$ ? We know $\oplus P\subseteq FP^{\#P}$ What are some barriers to proving this inclusion $\oplus P\subseteq\...
Turbo's user avatar
  • 13k
0 votes
0 answers
57 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
2 votes
1 answer
229 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
  • 542
0 votes
1 answer
101 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
  • 111
7 votes
1 answer
424 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, ...), ...
Manish Kumar's user avatar
0 votes
0 answers
48 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
157 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
  • 13k
1 vote
0 answers
77 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
73 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
360 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
93 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
  • 133
1 vote
0 answers
68 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
41 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
135 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
94 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
10 votes
2 answers
639 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
44 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
58 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
  • 13k
1 vote
0 answers
68 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
69 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
70 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
3 votes
1 answer
80 views

What are some practical applications of inductive-inductive and inductive-recursive types?

Since this question got not many answers Im hoping asking again could convey that this has some importance. Anyway so in undergraduate education, I was working on research to implement dependent-...
AnonymousThunk's user avatar

15 30 50 per page