user avatar
user avatar
user avatar
Matt Groff
  • Member for 11 years, 10 months
  • Last seen more than a month ago
25 votes
3 answers
2k views

Has there been any research on $k$-SAT above the satisfiability threshold?

20 votes
1 answer
765 views

How close can we get to linear multiply, add, and compare (on integers)?

11 votes
3 answers
794 views

Where do I turn for help with research/publishing?

11 votes
2 answers
792 views

Are quasi-polynomial sized circuits for 3-SAT trivial?

9 votes
2 answers
393 views

Information on k-SAT (Introduction, Bounds, Methods, etc.)

7 votes
0 answers
248 views

How quickly can we find an arbitrary digit in multiplication?

7 votes
2 answers
322 views

The worst-case scenario(s) for MAX3E SAT

7 votes
1 answer
104 views

How quickly can we perform base extension in a residue number system?

7 votes
2 answers
427 views

What are the current best upper bounds of #P?

7 votes
0 answers
150 views

What's the upper bounds for #3-SAT circuits?

6 votes
5 answers
284 views

What is/are the lower bounds for finding a something akin to complex residue?

6 votes
0 answers
264 views

The latest concerning Valiant-Vazirani

5 votes
1 answer
500 views

What is the running time of taking a limit?

5 votes
0 answers
157 views

Satisfiability threshold and partially random formulas

5 votes
1 answer
95 views

How quickly can we decompose a number into a set of residues?

5 votes
1 answer
588 views

Can we confirm that 2-SAT can indeed be transformed into Horn-SAT in this manner?

3 votes
0 answers
175 views

Fast way of getting a matrix of sums

3 votes
0 answers
64 views

How fast can we group clauses with few variables in common in k-SAT?

3 votes
2 answers
133 views

How well can we do with this variable assignment problem?

2 votes
0 answers
164 views

Is SAT in $c^{\sqrt{n}}$ time with preprocessing worthwhile?

2 votes
0 answers
96 views

How fast can we perform DFT on a Log-RAM computer?

2 votes
0 answers
247 views

Is putting articles on arXiv or alternatives, before peer review, generally acceptable?

2 votes
0 answers
127 views

What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?

2 votes
0 answers
86 views

#2-SAT or 3-SAT and variable that appears most often

2 votes
0 answers
90 views

Forming Sets from 3-SAT Clauses

1 vote
0 answers
33 views

Are there uses for a Fourier transform of length $n^m$ with elements of maximum size $n$?

1 vote
1 answer
698 views

Learning about EXPTIME and EXPSPACE

1 vote
1 answer
210 views

Can an oracle allowing errors be non-relativizing?

0 votes
1 answer
186 views

What is known about NP hard problems that access preprocessed information?

0 votes
0 answers
135 views

Does this meet the space requirements for the lower 3-SAT bounds?