Hottest Questions This Month

7

votes

2

answers

134

views

Algebraic characterisation of star-free safety languages

modified Oct 7 at 14:36 Denis 7,430

5

votes

1

answer

112

views

star height of star-free languages

fl.formal-languages regular-language regular-expressions monoid

modified Oct 19 at 11:12 Denis 7,430

4

votes

1

answer

96

views

Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$

complexity-classes polynomial-hierarchy

answered yesterday Emil Jeřábek 13.6k

3

votes

1

answer

94

views

Regular Expressions that converts into unambiguous automata

reference-request automata-theory regular-language regular-expressions

answered Oct 14 at 18:11 MRC 196

6

votes

1

answer

263

views

Cook inspiration for NP completeness

cc.complexity-theory np-complete cook-levin

modified Oct 12 at 7:41 Rodrigo 717

4

votes

1

answer

174

views

Upper bound on the expected number of correct bits via a "lossy compression"

it.information-theory kolmogorov-complexity upper-bounds

answered Oct 2 at 13:19 mathworker21 220

1

vote

1

answer

102

views

Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?

ds.algorithms graph-theory graph-algorithms

answered Oct 16 at 7:26 David Eppstein 50k

5

votes

1

answer

165

views

Lower bound for the OR problem

reference-request time-complexity lower-bounds sample-complexity

answered Oct 23 at 12:01 user2316602 570

1

vote

1

answer

160

views

State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

graph-theory graph-algorithms approximation-algorithms approximation max-cut

answered Oct 9 at 20:46 Jukka Suomela 11.2k

2

votes

1

answer

105

views

exact path cover for undirected graph

graph-theory graph-algorithms

answered Oct 15 at 1:30 Chandra Chekuri 6,430

1

vote

1

answer

114

views

Divide and Conquer Algorithm for 1-Median Problem

ds.algorithms lower-bounds clustering

modified Oct 6 at 11:04 Inuyasha Yagami 1,306

8

votes

0

answers

145

views

Can exponential-size depth-2 $CC^0[m]$ circuits with generalized $MOD_m$ gates compute arbitrary functions from $Z/mZ$ to $Z/2Z$?

circuit-complexity universal-computation

modified Oct 19 at 19:49 Jake 442

3

votes

1

answer

67

views

Encapsulation of OOP and referential transparency of functional programming

functional-programming object-oriented

answered Oct 4 at 7:52 Andreas Rossberg 1,280

3

votes

1

answer

134

views

Does a graph resulting from the union of triangles has a particular name?

graph-theory ds.data-structures

modified Oct 22 at 19:28 mhum 3,342

-1

votes

1

answer

75

views

Non-(PAC)-Learnable Classes

pac-learning

modified Oct 6 at 7:37 Aryeh 9,692

3

votes

0

answers

150

views

Any problems for which we know the complexity, but no algorithms with the same time?

proofs complexity

asked Oct 17 at 0:19 MinusPi 49

9

votes

0

answers

115

views

Complexity of NFA to DFA minimization with binary threshold

automata-theory minimization

asked Oct 17 at 8:12 Shaull 5,057

5

votes

0

answers

108

views

Halting problem for finitary PCF

computability pl.programming-languages semantics undecidability

modified Oct 3 at 18:18 Andrej Bauer 25.7k

0

votes

1

answer

106

views

Derandomizing arbitrary width read-many and ordered branching programs?

cc.complexity-theory randomness derandomization space-bounded pseudorandom-generators

modified Oct 14 at 15:31 Mr. 11.8k

0

votes

0

answers

110

views

Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?

np-hardness sat reductions boolean-formulas

asked Oct 1 at 21:23 ferris 1

2

votes

0

answers

99

views

Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover

cc.complexity-theory ds.algorithms graph-algorithms parameterized-complexity exp-time-algorithms

modified Oct 16 at 16:55 Naysh 322

1

vote

0

answers

96

views

Does any physical process constitute a "computation"? [closed]

turing-machines it.information-theory universal-computation church-turing-thesis

asked Oct 11 at 17:57 dnnct 27

5

votes

0

answers

72

views

Fine-Grained Hardness for Undirected Hamiltonicity

cc.complexity-theory ds.algorithms graph-algorithms hamiltonian-paths fine-grained

asked Oct 12 at 19:04 Naysh 322

1

vote

1

answer

92

views

Maximally Permissive Strategies for Safety Properties

linear-temporal-logic omega-language

answered Oct 8 at 23:53 Denis 7,430

1

vote

1

answer

51

views

Maximize the absolute value of connected nodes after $k$ modifications

np-hardness optimization

modified Oct 8 at 18:46 Neal Young 7,397

3

votes

0

answers

82

views

Why is the ellipsoid method numerically unstable?

linear-programming

asked Sep 29 at 16:54 user3508551 440

2

votes

0

answers

76

views

On-line pagerank in a streaming DAG (Directed Acyclic Graph)

graph-algorithms directed-acyclic-graph online-algorithms streaming-algorithms topological-sorting

asked Oct 7 at 9:30 Matthieu Latapy 683

0

votes

0

answers

75

views

Using the probabilistic method to fill the gaps in a proof of set disjointness

pr.probability randomized-algorithms communication-complexity

asked Oct 22 at 5:39 Arun 11

2

votes

1

answer

72

views

Can this special case of Node Weighted Steiner Tree be solved in polynomial time?

graph-theory graph-algorithms np-hardness approximation-algorithms

modified Oct 7 at 2:24 Karagounis Z 473

0

votes

0

answers

69

views

Large CLIQUE approximation

reference-request approximation-hardness clique

asked Oct 2 at 7:57 Bolton Bailey 101

-2

votes

0

answers

68

views

Example of any non-NP decision problem without invoking time-hierarchy theorem

np

asked Oct 15 at 21:37 Monty Thibault 7

1

vote

0

answers

66

views

Recovering the inputs to Boolean circuits after partial evaluation

cc.complexity-theory lo.logic circuit-complexity

modified 2 days ago ShyPerson 382

2

votes

0

answers

66

views

Computational Complexity of MIN-EQ-3-CNF

cc.complexity-theory polynomial-hierarchy

modified yesterday Lieuwe Vinkhuijzen 1,584

1

vote

0

answers

65

views

converse form of chernoff bound

pr.probability randomness chernoff-bound

asked 2 days ago Annonymous 243

1

vote

1

answer

48

views

An easy computable injection with a hard inverse

cc.complexity-theory reversible-computing

answered 15 hours ago Alexander Tenenbaum 129

-2

votes

0

answers

61

views

Approximating the number of triangles using $\ell_0$ sampling

counting-complexity streaming-algorithms

asked Oct 5 at 8:32 felipa 187

-1

votes

0

answers

60

views

A Special case of Weighted Set Cover Problem

approximation-algorithms set-cover

modified Oct 3 at 16:10 Arash Vaezi 1

-1

votes

0

answers

57

views

The parameterized complexity of proper edge-colored spanning tree

parameterized-complexity treewidth

modified Oct 21 at 5:01 zhukui bai 1

0

votes

0

answers

56

views

What's an interpreter? [closed]

ct.category-theory compilers

modified 20 hours ago Corbin 215

-2

votes

0

answers

53

views

Show a class of hypothesis is not PAC-learning (realizable)

pac-learning

asked Oct 3 at 16:11 M. Fire 1

1

vote

0

answers

52

views

What is the expected treewidth of a large-treewidth graph intersected with Erdos-Renyi graph?

graph-theory treewidth

asked Oct 20 at 11:53 Artur Riazanov 299

1

vote

0

answers

52

views

Canonical tester for dense graphs: from tester to removal lemma?

reference-request property-testing

modified Oct 10 at 4:53 Clement C. 4,083

-1

votes

0

answers

51

views

Mentally mapping between Turing machines and formal systems [closed]

lo.logic fl.formal-languages turing-machines

asked 2 days ago fibonaccho 1

0

votes

0

answers

49

views

Minimal lexicographical path on DAG in O(||V| + |E|)

graph-theory graph-algorithms shortest-path

modified Oct 4 at 12:44 unknown constant 11

0

votes

0

answers

48

views

Finding the best $k-$subset which maximizes a matrix sum

optimization time-complexity

asked Oct 2 at 15:13 Samrat Mukhopadhyay 101

0

votes

0

answers

48

views

k-Median Problem With Restricted Centers

approximation-algorithms clustering

asked Oct 18 at 19:30 Inuyasha Yagami 1,306

-2

votes

0

answers

45

views

Parameterized complexity of problems related to trees

graph-algorithms parameterized-complexity spanning-tree

asked Oct 23 at 14:11 zhukui bai 1

Top Questions

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