Most Popular
1500 questions
16
votes
2 answers
Integer programming with a fixed number of variables
The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of the data.
I interpret that as follows.
Integer…
Bernhard Kausler
- 263
- 2
- 7
16
votes
3 answers
Are vertex colourings--in a sense--edge colourings?
We know that edge colourings of a graph $G$ are vertex colourings of a special graph,
namely of the line graph $L(G)$ of $G$.
Is there a graph operator $\Phi$ such that vertex colourings of a graph $G$ are
edge colourings of the graph $\Phi(G)$ ?…
user13136
- 2,477
- 1
- 24
- 24
16
votes
2 answers
Outstanding conjectures and open problems in (algorithmic) game theory?
What sort of conjectures and major open problems are the most important in algorithmic game theory (or game theory in general as it relates to CS)? For example, the resolution of NASH as being PPAD-complete would, I think, have been the biggest one…
daveagp
- 1,100
- 7
- 14
16
votes
1 answer
Natural candidates for the hierarchy inside NPI
Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems conjectured to be $\mathsf{NPI}$ here.
Ladner's…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
16
votes
4 answers
Worst number of questions needed to learn a monotonic predicate over a poset
Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by providing one node $x \in X$ and finding out if $P(x)$…
a3nm
- 9,269
- 27
- 86
16
votes
10 answers
Applications of Game theory in computer science?
As a computer science student, I have been introduced to game theory, but not seen much detail on the subject. I have searched on Google and looked at some books about game theory and they provided confirmation of its usage in computer science. I…
S. M. Shahinul Islam
- 261
- 1
- 2
- 10
16
votes
3 answers
What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?
I am reading the classic "Hardness vs Randomness" by Nisan and Wigderson. Let $B=\{0,1\}$, and fix a function $l\colon \mathbb{N} \to \mathbb{N}$. They define a family of functions $G = \{G_n : B^{l(n)} \to B^n\}$ to be pseudorandom in case for…
user12484
- 163
- 4
16
votes
2 answers
Robustness of splitting a junta
We say that a Boolean function $f: \{0,1\}^n \to \{0,1\}$ is a $k$-junta if $f$ has at most $k$ influencing variables.
Let $f: \{0,1\}^n \to \{0,1\}$ be a $2k$-junta. Denote the variables of $f$ by $x_1, x_2, \ldots, x_n$. Fix
$$S_1 = \left\{ x_1,…
user887
16
votes
1 answer
Complexity of recognizing vertex-transitive graphs
I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result.
Question 1. Let $G$ be a simple undirected graph of order $n$. What is the
computational complexity (in terms of $n$) of…
Jernej
- 651
- 4
- 10
16
votes
2 answers
How to show that a type in a system with dependent types is not inhabited (i.e. formula not provable)?
For systems without dependent types, like Hindley-Milner type system, the types correspond to formulas of intuitionistic logic. There we know that its models are Heyting algebras, and in particular, to disprove a formula, we can restrict to one…
Petr
- 2,601
- 15
- 28
16
votes
3 answers
Smallest set that intersects some given sets
Let $S_1,S_2,\ldots,S_n$ be sets that may have elements in common. I'm looking for a smallest set $X$ such that $\forall i,\,X\cap S_i \ne \emptyset$.
Does this problem have a name? Or does it reduce to some known problem?
In my context…
adl
- 302
- 1
- 7
16
votes
1 answer
Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?
This is a follow up to this question, and is related to this question of Shiva Kinali.
It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use hierarchy theorems. I want to know if the proofs are…
Kaveh
- 21,577
- 8
- 82
- 183
16
votes
3 answers
Are there any classes of functions which require provably different resources to compute versus computing their inverse?
Apologies in advance if this question is too simple.
Basically, what I want to know is if there are any functions $f(x)$ with the following properties:
Take $f_n(x)$ to be $f(x)$ when the domain and codomain are restricted to $n$-bit strings.…
Joe Fitzsimons
- 13,675
- 47
- 91
16
votes
1 answer
Speedup from algorithmic advances vs. hardware
I recall seeing a study or article a while ago claiming that most of the speedup seen in computer programs over the last several decades is from better algorithms rather than faster hardware. Does anyone know the study or article?
John
- 323
- 1
- 6
16
votes
1 answer
What is the complexity of rectangle packing when rotations are allowed?
In the rectangle packing problem, one is given a set of rectangles $\{r_1,\dots,r_n\}$ and bounding rectangle $R$. The task is to find a placement of $r_1,\ldots,r_n$ inside $R$ such that none of the $n$ rectangles overlap.
Generally, the…
Adam Paetznick
- 640
- 4
- 8