Skip to main content
Share Your Experience: Take the 2024 Developer Survey
12 votes
Accepted

How stringent is the peer review process of ECCC exactly?

ECCC is supposed to reject any paper that is submitted without something that appears to be a proof for all of the main theorems. There is no expectation that a board member is going to check that ...
Eric Allender's user avatar
4 votes

Reference request: finite field computation over the Word-RAM model

Looks like Lemma 2.6 from https://arxiv.org/abs/2403.20326 answers my question. Constant time addition and multiplication are possible over $\mathbb{F}_q$ in the Word-RAM model, provided you first ...
Naysh's user avatar
  • 686
3 votes
Accepted

Hierarchy of classes between NP and NEXP

$\let\R\mathrm$The nondeterministic time hierarchy theorem, which is the reason $\R{NP\ne NEXP}$ in the first place, immediately gives you infinitely many (even $2^{\aleph_0}$) classes intermediate ...
Emil Jeřábek's user avatar
1 vote
Accepted

Constructing vector valued boolean circuits from boolean circuits

I doubt it. At least, not in all cases. Suppose that you are working in a circuit model where every function $\mathbb{B}^k\to\mathbb{B}$ can be represented by a circuit with $\le 2^k+1$ gates, say by ...
D.W.'s user avatar
  • 12.1k

Only top scored, non community-wiki answers of a minimum length are eligible