Hottest Questions This Month

4

votes

2

answers

756

views

Attempted proofs of P vs NP

cc.complexity-theory

modified Jun 2 at 20:08 SamM 1,217

12

votes

1

answer

329

views

+50

Deterministic error reduction, state-of-the-art?

answered Jun 18 at 3:08 guest 31

5

votes

1

answer

159

views

Correctness of AKS algorithm for shortest vector problem

randomized-algorithms exp-time-algorithms integer-lattice correctness

answered Jun 12 at 2:38 Sasho Nikolov 16.5k

3

votes

1

answer

112

views

Reductions in Descriptive Complexity

lo.logic reductions descriptive-complexity

modified May 31 at 8:26 Jan Johannsen 3,894

3

votes

2

answers

168

views

How do continuations represent negations (under the Curry–Howard correspondence)?

lo.logic type-theory proof-theory continuations curry-howard

modified Jun 14 at 12:59 Dan Doel 381

5

votes

1

answer

164

views

Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power

cc.complexity-theory circuit-complexity polynomials

modified 2 days ago Cyrus Rashtchian 31

5

votes

1

answer

68

views

Complexity of Finding Largest Set of Intersecting Convex Polytopes

np-hardness linear-programming polytope

answered Jun 20 at 13:23 Gamow 4,182

2

votes

1

answer

87

views

Verified type checkers

pl.programming-languages type-theory program-verification type-inference

answered Jun 5 at 7:27 Andrej Bauer 22.4k

1

vote

1

answer

107

views

Count satisfying assignments of CNF formulas over all possible negation assignments

cc.complexity-theory approximation-algorithms sat counting-complexity

answered Jun 17 at 13:46 Emil Jeřábek 10.4k

7

votes

1

answer

71

views

Simple proof that splay trees have the dynamic finger property?

reference-request ds.data-structures

answered Jun 4 at 20:58 László Kozma 636

-2

votes

1

answer

102

views

Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?

cc.complexity-theory complexity-classes counting-complexity

modified 22 hours ago Lieuwe Vinkhuijzen 1,000

2

votes

1

answer

117

views

Maximum Positive Negative Set Cover Problem

approximation-hardness

modified Jun 20 at 5:45 Yonatan N 1,187

2

votes

1

answer

99

views

Why not include private randomness in internal communication information definition?

it.information-theory communication-complexity

answered Jun 11 at 11:40 Or Meir 4,070

5

votes

1

answer

97

views

k-testable languages with non-constant k?

reference-request fl.formal-languages

modified Jun 9 at 18:52 Michaël Cadilhac 2,601

6

votes

0

answers

132

views

Planar Exact Cover by even-size sets

cc.complexity-theory np-hardness

modified Jun 19 at 16:03 Yota Otachi 1,340

0

votes

1

answer

102

views

Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?

ds.algorithms factoring heuristics

modified Jun 19 at 19:52 orgesleka 266

0

votes

0

answers

153

views

On planar $4$ regular graphs

graph-colouring average-case-complexity

modified Jun 1 at 4:16 Turbo 5,090

2

votes

1

answer

89

views

Difference between statically and dynamically typed languages

type-systems

modified Jun 1 at 21:58 Martin Berger 9,335

8

votes

0

answers

100

views

Diameter of “almost” always connected Erdős-Renyi graphs

random-graphs diameter

asked May 30 at 13:39 Lamine 760

1

vote

0

answers

121

views

Can a hash preimage be used to amplify BPP probabilities?

cc.complexity-theory hash-function

modified May 28 at 15:38 Mark S 412

3

votes

1

answer

67

views

Agnostic query learning for DFAs

automata-theory machine-learning lg.learning query-complexity

answered May 28 at 18:20 Clement C. 2,208

1

vote

1

answer

86

views

How many samples are needed to reconstruct a path?

ds.algorithms graph-theory graph-algorithms machine-learning sample-complexity

answered May 28 at 16:14 Emil Jeřábek 10.4k

1

vote

1

answer

109

views

Is the unbounded fan-in model realistic?

cc.complexity-theory circuit-complexity circuits

answered May 29 at 20:27 Stella Biderman 712

-1

votes

0

answers

104

views

Prove that 3SAT50 is NP-Complete [closed]

sat turing-machines reductions

modified Jun 14 at 12:45 Yamar69 59

0

votes

0

answers

103

views

Oracle separation between PH and PSPACE

oracles complexity

modified Jun 14 at 21:06 BlackHat18 7

-1

votes

1

answer

44

views

Min Cut with Vertices

graph-theory graph-algorithms

answered Jun 6 at 12:37 smapers 81

4

votes

0

answers

93

views

Expected vs actual amount of information leaked by an $l$-bits message

it.information-theory communication-complexity

modified Jun 10 at 22:41 D.W. 7,536

3

votes

0

answers

87

views

Examples of ineffective PH collapse theorems?

big-list polynomial-hierarchy

modified Jun 20 at 6:31 Geoffrey Irving 1,602

2

votes

1

answer

85

views

Lower bound on the worst-case unbiased coin flips to sample a distribution?

reference-request randomness

modified Jun 7 at 18:16 Clement C. 2,208

5

votes

0

answers

66

views

Complexity of a specific class of definite integrals

np-hardness computing-over-reals

asked Jun 2 at 7:57 Leonardo 41

0

votes

0

answers

81

views

How much computer science / software experience is needed for a math major to do work in AI?

ai.artificial-intel se.software-engineering

modified Jun 6 at 7:25 Jan Johannsen 3,894

4

votes

0

answers

81

views

Where in $PH$ are these problems?

coding-theory polynomial-hierarchy

asked Jun 13 at 2:32 Turbo 5,090

1

vote

1

answer

63

views

Embedding a n-tree into a b-dimensional space

optimization computational-geometry

modified Jun 5 at 16:26 jackb 138

1

vote

1

answer

49

views

QPIP minimal client quantum capabilities

quantum-computing quantum-information interactive-proofs

modified Jun 6 at 0:27 Avi Tal 406

2

votes

0

answers

80

views

Is $MSB$ of permanent and certifying half number of witnesses easy?

cc.complexity-theory permanent

modified Jun 12 at 9:26 Turbo 5,090

0

votes

0

answers

79

views

Is it possible to sort by only knowing the sign of pairwise sums?

cc.complexity-theory ds.algorithms sorting

modified Jun 14 at 8:09 multiplex 6

2

votes

0

answers

78

views

A question about UE

exp-time-algorithms nexp unique-solution

asked Jun 1 at 19:55 user3483902 473

1

vote

0

answers

70

views

How does Best Partition Communication Complexity behave under input transformations?

communication-complexity

modified Jun 10 at 10:13 verifying 485

1

vote

0

answers

67

views

Agnostic query learning of decision trees

machine-learning lg.learning fourier-analysis pac-learning

asked Jun 4 at 8:28 Aryeh 6,074

2

votes

0

answers

65

views

Looking for Research in Cryptographic Computing

complexity security

asked Jun 11 at 14:24 Kevin Dolan 283

-1

votes

0

answers

63

views

Validity of relativization argument

cc.complexity-theory oracles p-vs-np relativization

modified May 27 at 17:07 tech hacks 1

0

votes

0

answers

62

views

What is sequence unification?

lo.logic

asked Jun 16 at 2:20 Björn Lindqvist 229

5

votes

0

answers

48

views

Hardness result or reference for optimal Gaussian elimination process

reference-request linear-algebra np-complete boolean-matrix

modified May 26 at 13:35 Emil Jeřábek 10.4k

0

votes

0

answers

60

views

Does there exist an undecidable problem such that the answer is YES for exactly one TM, and NO for all others? [on hold]

computability turing-machines undecidability universal-turing-machines

modified 2 days ago user138901 105

-2

votes

0

answers

55

views

Closure of rational langages under morphisms

fl.formal-languages automata-theory

asked Jun 11 at 21:35 Tchae 1

1

vote

0

answers

55

views

Straight line programs with $\sqrt{~}$

arithmetic-circuits

modified Jun 3 at 20:33 Clement C. 2,208

1

vote

0

answers

51

views

Graph automorphism with prescribed values

cc.complexity-theory graph-theory graph-algorithms graph-isomorphism

asked May 30 at 13:42 Mike Hawk 106

Top Questions

Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.