Hottest Questions Today

1

vote

1

answer

48

views

An easy computable injection with a hard inverse

answered 13 hours ago Alexander Tenenbaum 129

0

votes

0

answers

55

views

What's an interpreter? [closed]

modified 18 hours ago Corbin 215

4

votes

1

answer

95

views

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

complexity-classes polynomial-hierarchy

answered yesterday Emil Jeřábek 13.6k

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

votes

0

answers

33

views

Can you swap adjacent elements [A, B] in a topological sort if A is not a direct predecessor of B in the partial order? [closed]

topological-sorting

modified yesterday oleshkowitz 1

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

-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

1

vote

0

answers

65

views

converse form of chernoff bound

pr.probability randomness chernoff-bound

asked 2 days ago Annonymous 243

-1

votes

0

answers

28

views

temperal communication network [closed]

ni.networking-internet

asked 2 days ago JayRugMan 1

-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

-1

votes

0

answers

30

views

Steiner Tree Problem for circle graph

graph-algorithms

asked Oct 23 at 13:33 Zhang Yu 1

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

-1

votes

0

answers

17

views

Understanding the behavior of Conflict Serializability and View Serializability with respect to blind writes

db.databases

asked Oct 23 at 6:43 Abhishek Ghosh 99

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

5

votes

1

answer

111

views

star height of star-free languages

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

modified Oct 19 at 11:12 Denis 7,430

-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

31

views

Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?

reference-request graph-theory graph-algorithms approximation-algorithms optimization

asked Oct 21 at 7:44 Karagounis Z 473

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

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

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

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

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

3

votes

0

answers

149

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

-3

votes

0

answers

43

views

Permutation Graphs is Chordal?

graph-theory graph-isomorphism graph-colouring

asked Oct 18 at 8:42 R.hatam 15

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

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

-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

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

-3

votes

0

answers

37

views

Asymptotic Analysis of code that are unusual [closed]

asymptotics

asked Oct 16 at 18:17 achen 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

7

votes

2

answers

134

views

Algebraic characterisation of star-free safety languages

reference-request fl.formal-languages omega-language

modified Oct 7 at 14:36 Denis 7,430

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

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

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

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

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

2

answers

107

views

Status of certain problems in knot theory

reference-request np-hardness cg.comp-geom topology

answered Oct 12 at 12:46 Arnaud 790

0

votes

0

answers

30

views

Bounded-Frequency Minimum Set Cover Problem

graph-theory np-hardness np-complete set-cover upper-bounds

asked Oct 12 at 5:06 Garrett 101

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

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

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

-1

votes

1

answer

75

views

Non-(PAC)-Learnable Classes

pac-learning

modified Oct 6 at 7:37 Aryeh 9,692

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

4

votes

1

answer

173

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

4

votes

1

answer

260

views

Pagerank in directed acyclic graphs (DAG)

graph-theory graph-algorithms directed-acyclic-graph data-mining ni.networking-internet

modified Oct 7 at 9:38 Matthieu Latapy 683

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

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

Top Questions

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