Hottest Questions Today

3

votes

0

answers

13

views

Complexity of Encoding a Matroid Flow Problem in a Matrix

asked 8 hours ago Naysh 365

0

votes

0

answers

33

views

Complexity of Edge Coloring Regular Graphs With Large Degrees

cc.complexity-theory graph-algorithms graph-colouring

asked 16 hours ago Tacocat 1

1

vote

1

answer

82

views

Publishing by showing falsity of existing results [closed]

soft-question

modified yesterday 1.. 11k

0

votes

0

answers

55

views

+50

Proof that quantum computers can't easily invert permutations

lower-bounds

modified 3 hours ago AngryLion 29

-1

votes

0

answers

17

views

Feed-Forward artificial neural network memorization

machine-learning

asked 22 hours ago keyboardAnt 1

5

votes

1

answer

141

views

Proof of $LP$ is in $coNP$ without showing it is in $P$?

cc.complexity-theory linear-programming

modified yesterday Yonatan N 1,525

10

votes

1

answer

315

views

Can we derive Cubical Type Theory from Self-Types?

type-theory lambda-calculus calculus-of-constructions homotopy-type-theory

modified yesterday Rotsor 103

3

votes

1

answer

180

views

Entropy-like quantity

reference-request shannon-entropy

answered 16 hours ago Bjørn Kjos-Hanssen♦ 4,288

3

votes

1

answer

70

views

When is it hard to invert a sparse matrix?

linear-algebra sparse-matrix linear-equations

answered yesterday Thomas Klimpel 2,898

-1

votes

0

answers

17

views

Is there a naming scheme for an arbitrary number of nodes on a tree with an arbitrary number of branches and roots?

tree

modified yesterday NAccumbens 1

-3

votes

0

answers

44

views

Reducing a problem to the MST problem

graph-algorithms spanning-tree

modified 2 days ago dv55 103

0

votes

0

answers

23

views

Finding the smallest-cost way to deliver goods

reductions spanning-tree

asked yesterday Wan 1

1

vote

1

answer

94

views

Dependence of decidability on the encoding of Turing machines

turing-machines decidability

modified 2 days ago Aryeh 8,389

3

votes

0

answers

67

views

Is there a known notion of “stochastic dependent pair”?

type-theory pr.probability dependent-type denotational-semantics

modified 2 days ago phipsgabler 199

1

vote

0

answers

29

views

What is the time complexity of substitution algorithms(normalization by evaluation, explicit subtitution)?

lambda-calculus functional-programming

asked 2 days ago user42215 119

-3

votes

0

answers

17

views

bhs problem on anonymous ring

dc.distributed-comp

asked Sep 21 at 10:07 user689507 1

17

votes

0

answers

189

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?

ds.algorithms matrices computational-geometry search-problem boolean-matrix

modified Sep 18 at 19:44 Michael Wehar 4,339

8

votes

1

answer

184

views

Can you find a counter-example for this proposed Graph Isomorphism algorithm?

graph-isomorphism puzzles

answered Sep 19 at 8:43 Joshua Grochow 33.2k

4

votes

1

answer

98

views

Given a domain, how do we build a language whose denotation is the domain?

ct.category-theory denotational-semantics domain-theory

answered Sep 19 at 23:05 Andrej Bauer 24.3k

1

vote

1

answer

68

views

Are there non trivial 2-basis of a 2-connected planar graph?

planar-graphs

modified Sep 17 at 21:13 David Eppstein 48.9k

7

votes

1

answer

228

views

Testing for finite expectation

reference-request machine-learning lg.learning st.statistics

modified Sep 16 at 22:36 Hermann Gruber 4,939

-2

votes

0

answers

52

views

How well can directed multicut be approximated? [closed]

graph-algorithms approximation-algorithms directed-acyclic-graph

modified Sep 19 at 20:49 user122938 17

1

vote

0

answers

38

views

On automorphism group of quantum error correcting codes

reference-request soft-question quantum-computing coding-theory algebra

modified Sep 18 at 15:04 Root 195

-2

votes

1

answer

56

views

Hardness of maximizing difference of functions [closed]

cc.complexity-theory np-hardness optimization

modified Sep 17 at 16:03 Christian Komusiewicz 935

0

votes

0

answers

83

views

Algorithms and approximations for optimal offline binary tree operations

ds.algorithms approximation-algorithms optimization binary-trees

modified Sep 19 at 16:13 Mario Carneiro 133

1

vote

0

answers

69

views

λProlog vs HiLog

lo.logic pl.programming-languages type-theory logic-programming

modified Sep 16 at 17:21 MaxB 221

7

votes

1

answer

128

views

Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

cc.complexity-theory graph-algorithms automata-theory graph-isomorphism directed-acyclic-graph

modified Sep 12 at 22:39 daniello 2,801

-2

votes

0

answers

53

views

How to reduce any NP-Complete problem to SAT problem [closed]

co.combinatorics np-complete p-vs-np

asked Sep 16 at 9:11 SUBHIGYA PRIYANSH 1

5

votes

0

answers

94

views

Exact algorithms for $k$-means

reference-request optimization clustering

modified Sep 15 at 21:48 Andrea 151

1

vote

0

answers

35

views

Computing chromatic number of subcubic graphs

graph-colouring

asked Sep 16 at 16:03 Cyriac Antony 829

0

votes

0

answers

45

views

Calculation of sum of weights of nodes in a tree graph

graph-algorithms ds.data-structures

modified Sep 16 at 11:55 boldnik 101

0

votes

1

answer

51

views

Common solutions to 3SAT and 2SAT models comprised of the same variables

cc.complexity-theory sat 2sat

answered Sep 15 at 16:19 D.W. 9,268

16

votes

2

answers

434

views

Publishing short and simple results

soft-question

answered Sep 11 at 20:47 Manu 7,281

0

votes

1

answer

43

views

Algorithm to calculate coordinated radio frequencies

ds.algorithms

answered Sep 15 at 5:33 D.W. 9,268

0

votes

0

answers

30

views

Harmonic analysis of sequences of Boolean functions (i.e. of words in $(\{0,1\}^n)^*$)

reference-request boolean-functions fourier-analysis

asked Sep 15 at 14:32 Shaull 4,158

0

votes

0

answers

38

views

Can a NEXP machine simulate invalid queries to a promise problem oracle?

complexity-classes time-complexity reductions promise-problems

modified Sep 15 at 9:58 user138901 351

5

votes

1

answer

75

views

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

ds.algorithms graph-theory graph-algorithms linear-programming enumeration

modified Sep 9 at 17:25 Neal Young 6,499

2

votes

0

answers

86

views

VC dimension of Voronoi cells (Manhattan distance)

combinatorics vc-dimension

modified Sep 12 at 6:31 AlexGj 46

4

votes

1

answer

212

views

3-SAT mixed with 2-SAT formulas

np-hardness sat monotone

modified Sep 6 at 22:43 Xavier Labouze 1,027

5

votes

0

answers

79

views

Separating QMA and QCMA

cc.complexity-theory

asked Sep 10 at 9:19 AngryLion 29

6

votes

0

answers

108

views

+100

Estimating the cardinality of multisets given some sets of different sizes

streaming-algorithms streaming

modified yesterday user1246462 79

2

votes

1

answer

77

views

Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices

cc.complexity-theory graph-theory

modified Sep 10 at 6:10 Cyriac Antony 829

Top Questions

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