Most Popular
1500 questions
16
votes
3 answers
Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?
I am a mathematician interested in set theory, ordinal theory, infinite combinatorics and general topology.
Are there any applications for these subjects in computer science?
I have looked a bit, and found a lot of applications (of course) for…
user135172
- 263
- 1
- 4
16
votes
3 answers
Why do constructivists not seem to care too much about call/cc
So a little while back I first had someone tell me that call/cc could allow proof objects for classical proofs by implementing Peirce's law. I did some thinking about the topic recently and I can't seem to find a flaw with it. However I can't really…
Jake
- 1,203
- 7
- 20
16
votes
1 answer
Is it enough to sort for polynomially many 0-1 sequences for a sorting network?
The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers.
Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence from S, then it sorts every 0-1 sequence and the…
domotorp
- 13,931
- 37
- 93
16
votes
7 answers
Research data organization
This is a question in the spirit of this one where I answered that it is important to keep track of what you have done something, why you have done it and what is not working.
I personally use notebooks for that purpose, but it has several…
Sylvain Peyronnet
- 3,063
- 1
- 18
- 29
16
votes
1 answer
Integer linear programming in logarithmic number of variables
I read that integer linear programming is solvable in polynominal time if the number $n$ of variables is fixed, i.e. $n \in O(1)$. If the number of variables grows logarithmically, i.e. $n \in O(\log_2(N))$ for a given input of size $N$, is the…
user3613886
- 261
- 1
- 2
16
votes
5 answers
Do "One Way Functions" have any applications outside crypto ?
A function $f \colon \{0, 1\}^* \to \{0, 1\}^*$ is one-way if $f$ can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm $A$,
$\Pr[f(A(f(x))) = f(x)] < 1/p(n)$
for every polynomial $p(n)$ and sufficiently…
Tarek Radwan
- 163
- 1
- 7
16
votes
2 answers
Is APX contained in NP?
A problem P is said to be in APX if there exists some constant c > 0 such that a polynomial-time approximation algorithm exists for P with approximation factor 1 + c.
APX contains PTAS (seen by simply picking any constant c > 0) and P.
Is APX in NP?…
Andrew W.
- 398
- 2
- 9
16
votes
2 answers
Does bit commitment yield oblivious transfer in the information-theoretic security model?
Suppose you have two arbitrarily powerful participants who don't trust each other. They have access to bit commitment (e.g., sealed envelopes containing data that one player can hand to the other but that can't be opened until the first player gives…
Peter Shor
- 24,763
- 4
- 93
- 133
16
votes
2 answers
Avalanche like stochastic process
Consider the following process:
There are $n$ bins arranged from top to bottom. Initially, each bin contains one ball. In every step, we
pick a ball $b$ uniformly at random and
move all the balls from the bin containing $b$ to the bin below it.
If…
Matthias
- 1,668
- 1
- 14
- 22
16
votes
1 answer
Minimal specification of Martin-Löf type theory
I'm reading the formal presentation of Martin-Löfs type theory (appendix of the HoTT book). The authors introduce a hierarchy of universes, then $\Pi, \Sigma,+, {\bf 0}, {\bf 1}$ and also $W$-types as well as natural numbers $\mathbb N$ (inductively…
Nikolaj-K
- 505
- 2
- 10
16
votes
3 answers
Are there knot theoretic formulations of NP complete problems?
Are there NP complete(or even NP-hard, or NP) problems that have good topological properties to study. Do NP problems have knot theoretic formulations? We know about #$P$ results about the Jones polynomial. Graph problems(embeddings?), specifically…
user3483902
- 1,261
- 7
- 13
16
votes
2 answers
Finding small sets of integers in which every element is a sum of two others
This is a follow-up to this question on math.stackexchange.
Let us say that a non-empty set S ⊆ ℤ is self-supporting if for every a ∈ S, there exist distinct elements b,c ∈ S such that a = b + c. For positive integers n, simple examples include the…
Niel de Beaudrap
- 8,821
- 31
- 70
16
votes
6 answers
Complexity of the Fisher-Yates Shuffle Algorithm
This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n).
In each iteration i, a random integer is chosen between…
Tomer Vromen
- 623
- 7
- 10
16
votes
2 answers
Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy
The $\mathsf{W}$-hierarchy is a hierarchy of complexity classes $\mathsf{W}[t]$ in parameterized complexity, see the Complexity Zoo for definitions. An alternative definition defines $\mathsf{W}[t]$ using weighted Fagin definability for…
Jan Johannsen
- 4,630
- 2
- 33
- 50
16
votes
1 answer
What are bounded-treewidth circuits good for?
One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output of a gate having $a$ as input (or vice-versa);…
a3nm
- 9,269
- 27
- 86