Hottest Questions Today

-2

votes

1

answer

100

views

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

modified 21 hours ago Lieuwe Vinkhuijzen 1,000

3

votes

0

answers

33

views

Algorithms for Maximum weight connected subgraph in planar graphs

reference-request graph-algorithms approximation-algorithms planar-graphs

asked yesterday Mathieu Mari 58

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

50

views

What exactly is the counting hierarchy (CH)? [on hold]

counting-complexity

asked Jun 21 at 8:32 Gurkenschurke66 1

5

votes

1

answer

67

views

Complexity of Finding Largest Set of Intersecting Convex Polytopes

np-hardness linear-programming polytope

answered Jun 20 at 13:23 Gamow 4,182

0

votes

0

answers

48

views

Lower bound for permutation generator

co.combinatorics lower-bounds

modified Jun 21 at 7:06 MrMartin 1

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

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

-1

votes

0

answers

21

views

Compression/Minimum Description Length of a Size $n$ List of Rational Numbers

it.information-theory coding-theory encoding

asked Jun 20 at 23:57 Dupin 1

2

votes

0

answers

45

views

Example of a hardness-of-approximation proof which improves the approximation factor?

cc.complexity-theory approximation-algorithms approximation-hardness

asked Jun 20 at 7:44 Elliot Gorokhovsky 317

0

votes

0

answers

31

views

Intersection of two deterministic parity automata

automata-theory

asked Jun 19 at 19:30 kafka 180

4

votes

0

answers

38

views

$\ell_\infty$ partially enclosing ball problem

computational-geometry

asked Jun 19 at 11:18 Aryeh 6,074

0

votes

0

answers

18

views

Algorithmic gap for greedy algorithm for (metric) uncapacitated facility location

approximation-algorithms optimization approximation-hardness

asked Jun 19 at 19:02 ydubey7 1

-3

votes

0

answers

34

views

A deterministic FA for $0^1^$ is required [closed]

regular-language dfa regular-expressions

asked Jun 18 at 18:02 user2925716 204

12

votes

1

answer

329

views

+50

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

reference-request randomness pseudorandomness expanders

answered Jun 18 at 3:08 guest 31

4

votes

0

answers

38

views

Hard family for degree-$D$ MAX-3LIN

sat approximation-hardness linear-equations

modified Jun 18 at 9:26 Abel Molina 1,324

0

votes

0

answers

46

views

Linear time algorithm for projective clustering

reference-request approximation-algorithms randomness computational-geometry clustering

modified Jun 17 at 14:58 Sudipta Roy 106

0

votes

0

answers

23

views

Two question regarding coreset construictions

reference-request approximation-algorithms randomness computational-geometry clustering

asked Jun 17 at 20:04 Sudipta Roy 106

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

0

votes

0

answers

62

views

What is sequence unification?

lo.logic

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

0

votes

0

answers

103

views

Oracle separation between PH and PSPACE

oracles complexity

modified Jun 14 at 21:06 BlackHat18 7

2

votes

1

answer

117

views

Maximum Positive Negative Set Cover Problem

approximation-hardness

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

18

votes

3

answers

2k

views

Why colon to denote that a value belongs to a type?

type-theory notation

modified May 28 at 8:00 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

-1

votes

0

answers

104

views

Prove that 3SAT50 is NP-Complete [closed]

sat turing-machines reductions

modified Jun 14 at 12:45 Yamar69 39

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

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

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

0

votes

0

answers

34

views

Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?

ds.data-structures

modified Jun 18 at 20:08 Peeyush Kushwaha 101

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

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

4

votes

2

answers

756

views

Attempted proofs of P vs NP

cc.complexity-theory

modified Jun 2 at 20:08 SamM 1,217

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

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

2

votes

0

answers

65

views

Looking for Research in Cryptographic Computing

complexity security

asked Jun 11 at 14:24 Kevin Dolan 283

-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

-3

votes

0

answers

27

views

minimum cost spanning tree algorithm with benchmark graphs

ds.algorithms

asked Jun 13 at 9:29 Jasmine Priskilla 1

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

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

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

2

votes

0

answers

38

views

AMQ (Bloom-filter like structure) lower bounds

optimization memory

asked Jun 10 at 18:52 haael 105

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

2

votes

0

answers

36

views

Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles

cc.complexity-theory graph-theory planar-graphs hamiltonian-paths

modified Jun 10 at 6:09 Lorenzo 440

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

1

vote

0

answers

38

views

relations between the degrees of a boolean function and its absolute function

boolean-functions fourier-analysis bounded-degree

asked Jun 9 at 14:05 user07001129 6

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

Top Questions

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