Michael Wehar

# 33 Questions

7
24
1
932
views

4
19
2
2k
views

2
18
0
407
views

### In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

Sep 18 at 19:44 Michael Wehar 4,800

17
1
602
views

1
15
2
1k
views

1
14
1
782
views

1
14
0
456
views

### Is there a P-complete language X such that succinct-X is in P?

Jan 25 '19 at 22:13 Frank Vega 119
1
14
1
305
views

5
14
0
612
views

### Does solving matrix multiplication in quadratic time imply that SETH is false?

Nov 27 '15 at 15:40 Michael Wehar 4,800
2
13
4
1k
views

2
11
1
278
views

2
10
1
202
views

1
10
1
309
views

9
1
185
views

2
9
1
601
views

9
0
421
views

### What are the best known reductions from SAT to CNF-SAT?

Mar 29 '17 at 18:53 Michael Wehar 4,800
1
9
0
139
views

### Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$

Mar 10 '17 at 3:35 Michael Wehar 4,800
1
9
1
239
views

5
8
3
610
views

8
1
298
views

3
8
0
266
views

### Given a Boolean formula, does there exist a small circuit that computes a satisfying assignment?

Apr 2 '17 at 22:27 Community 1
1
8
1
416
views

7
1
844
views

6
1
387
views

1
5
0
140
views

### How hard is it to generate a set of relatively prime numbers between two given bounds?

Jun 17 '18 at 19:46 Michael Wehar 4,800

5
1
914
views

1
5
0
829
views

### Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

Apr 9 '15 at 14:51 Michael Wehar 4,800
1
4
1
269
views

4
1
373
views

1
4