Most Popular
1500 questions
15
votes
2 answers
What is the following variation on Set Cover known as?
What is the following variation on set cover known as?
Given a set S, a collection C of subsets of S and a positive integer K, do there exist K sets in C such that every pair of elements of S lies in one of the selected subsets.
Note: It is not hard…
deinst
- 356
- 2
- 5
15
votes
2 answers
In the Hott book, are the most of the type formers redundant? And if so, why?
In chapter 1 and Appendix A of the Hott book, several primitive type families are presented (universe types, dependent function types, dependent pair types, Coproduct types, Empty Type, Unit type, natural number type, and identity types) to form the…
user833970
- 546
- 2
- 10
15
votes
0 answers
Differential privacy and data poisoning
A differentially private algorithm takes datasets containing inputs and produces randomized outputs, such that no small change in the dataset can shift the distribution of outputs by too much. This is normally discussed in the context of privacy -…
WuTheFWasThat
- 331
- 1
- 6
15
votes
1 answer
Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?
I expect the answer is no, but I could not actually construct a counterexample. The difference is that in $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$, we might not be able to pick an $O(n^{2+ε})$ algorithm uniformly in $ε$.
By a dovetailing argument (for…
Dmytro Taranovsky
- 2,577
- 1
- 10
- 24
15
votes
1 answer
Parallel Pebble Game on a Line
In the pebble game on a line there are N+1 nodes labelled 0 through N. The game starts with a pebble on node 0. If there is a pebble on node i, you can add or remove a pebble from node i+1. The goal is to place a pebble on node N, without placing…
Craig Gidney
- 1,518
- 9
- 21
15
votes
2 answers
Circuit Complexity Charaterization for DLogTime and NLogTime
$\mathsf{DLogTime}$ and $\mathsf{NLogTime}$ are two of the smallest complexity classes we have. (Note that logarithmic time hierarchy $\mathsf{LH}$ is equal to $\mathsf{AC}^0$ and these are the first two level of $\mathsf{LH}$).
After reading this…
Kaveh
- 21,577
- 8
- 82
- 183
15
votes
0 answers
Set Intersection lower bounds
Consider $S_1, ...,S_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S_i \cap S_j$ is empty or not. We would like to asnwer this in constant time. Under…
karmanaut
- 1,177
- 5
- 16
15
votes
1 answer
Example of logarithmic length witness being easier to verify than find
An easy observation is that if a problem $A$ is decidable by a polynomial-time nondeterministic program using $O(\log n)$ nondeterministic bits (i.e., all witnesses are logarithmic in length), then $A \in \mathsf{P}$.
If one then asks the question,…
Dave Doty
- 681
- 6
- 13
15
votes
2 answers
Is SAT a context-free language?
I am considering the language of all satisfiable propositional logic formulae, SAT (to ensure that this has a finite alphabet, we would encode propositional letters in some suitable way [edit: the replies pointed out that the answer to the question…
mak
- 504
- 2
- 14
15
votes
3 answers
Surveys on pseudo-random number generator design?
I am interested in generation of pseudo-random numbers for cryptography. Besides Chapter 5 of Menezes/Oorschot/Vanstone; Chapter 8 of Stinson; and Chapter 3 of Goldreich, where else could I find more? I'm interested in general principles for…
Jay
- 982
- 7
- 16
15
votes
1 answer
Validity of exponentiation in a polynomial time reduction
I asked this question 10 days ago on cs.stackexchange here but I didn'y have any answer.
In a very famous paper (in the networking community), Wang & Crowcroft present some $\mathsf{NP}$-completeness results of path computation under several…
Lamine
- 1,138
- 1
- 12
- 21
15
votes
2 answers
(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?
From a purely abstract math/computational reasoning point of view, (how) could one even discover or reason about problems like 3-SAT, Subset Sum, Traveling Salesman etc.,? Would we be even able to reason about them in any meaningful way with just…
PhD
- 5,305
- 5
- 25
- 40
15
votes
1 answer
The minimum number of arithmetic operations to compute the determinant
Has there been any work on finding the minimum number of elementary arithmetic operations needed to compute the determinant of an $n$ by $n$ matrix for small and fixed $n$? For example, $n=5$.
Simd
- 3,902
- 20
- 49
15
votes
2 answers
Status of Raghavendra's algorithm for solving linear systems in finite fields
In 2012, Lipton wrote a blog entry about a new algorithm for solving linear systems over finite fields by Prasad Raghavendra.
The link to Raghavendra's draft paper on the topic is now dead, and I can't find anything on the subject on Raghavendra's…
okintheory
- 253
- 1
- 4
15
votes
4 answers
Hierarchies in regular languages
Is there any known "nice" hierarchy $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (may be finite) inside the class of regular languages $L$? By nice here, the classes in each hierarchy capture different expressiveness / power / complexity. Also,…
raja.damanik
- 183
- 5