Most Popular
1500 questions
20
votes
2 answers
Explicit balanced matrix
Is it possible to build an explicit $N \times N$ $0/1$-matrix with $N^{1.5}$ ones such that every $N^{0.499} \times N^{0.499}$ submatrix contains less than $N^{0.501}$ ones?
Or probably it is possible to build an explicit hitting set for such…
ilyaraz
- 1,569
- 18
- 33
20
votes
4 answers
Is there current research into the implemention of Randomness Extractors?
Has there been research into implementing randomness extractor constructions?
It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making programmatic implementations potentially unrealistic.
Some…
Phillip Mates
- 485
- 2
- 7
20
votes
3 answers
Who introduced nondeterministic computation?
I have two historical questions:
Who first described nondeterministic computation?
I know that Cook described NP-complete problems, and
that Edmonds proposed that P algorithms are "efficient" or "good" algorithms.
I searched this Wikipedia…
user1338
20
votes
1 answer
How to prove that USTCONN requires logarithmic space?
USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input.
Omer Reingold showed that USTCONN is in L…
András Salamon
- 19,000
- 3
- 64
- 150
20
votes
4 answers
Parity and $AC^0$
Parity and $AC^0$ are like inseparable twins. Or so it has seemed for the last 30 years. In the light of Ryan's result, there will be renewed interest in the small classes.
Furst Saxe Sipser to Yao to Hastad are all parity and random restrictions.…
V Vinay
- 3,873
- 1
- 24
- 30
20
votes
2 answers
Is there a typed lambda calculus which is consistent and Turing complete?
Is there a typed lambda calculus where the corresponding logic under the Curry-Howard correspondence is consistent, and where there are typeable lambda expressions for every computable function?
This is admittedly an imprecise question, lacking a…
Morgan Thomas
- 461
- 2
- 8
20
votes
2 answers
How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$?
How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$? A polynomial time nondeterministic algorithm would immediately imply this because $P \neq EXPTIME$ but no one believes $NP = EXPTIME$. If…
Anonymous
- 201
- 1
- 2
20
votes
2 answers
Why isn't Montgomery modular exponentiation considered for use in quantum factoring?
It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is the preferred method. Modular exponentiation is…
S Huntsman
- 401
- 2
- 12
20
votes
5 answers
Deterministic Parallel algorithm for perfect matching in general graphs?
In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. And there are problems BELIEVED to be in…
Hsien-Chih Chang 張顯之
- 7,638
- 4
- 44
- 83
20
votes
5 answers
Version control for collaboration (with word-level diffs)?
Most papers are now written collaboratively, and collaborators are often located in different places. I have always used version control systems for my documents and code, and have also found version control critical for collaborative software…
András Salamon
- 19,000
- 3
- 64
- 150
20
votes
0 answers
Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?
The following question arose as a side product of some work I have been part of recently.
An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a circulant matrix and all its entries are either $0$…
Simd
- 3,902
- 20
- 49
20
votes
3 answers
Survey on algorithms/complexity of linear algebra
I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with emphasis on parallel ($NC$ hierarchy) and polytime…
Kaveh
- 21,577
- 8
- 82
- 183
20
votes
0 answers
Model-checking for three-variable logics and restricted structures
Denote the $k$-variable fragment of logic $L$ by $L^{(k)}$. The model-checking problem for a logic $L$ with respect to a class of structures $C$, denoted $MC(L,C)$, is the decision problem
$MC(L,C)$
Input: formula $\phi$ of $L$, structure $S$ from…
András Salamon
- 19,000
- 3
- 64
- 150
20
votes
0 answers
Weighted Hamming distance
Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is not necessarily Theoretical Computer Science but I think similar things come up sometimes, for instance in randomness…
Bjørn Kjos-Hanssen
- 4,485
- 2
- 25
- 40
20
votes
3 answers
Property testing in other metrics?
There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases:
$f$ is a member of some class of functions $\mathcal{C}$
$f$ is…
Aaron Roth
- 9,870
- 1
- 43
- 68