Hottest Questions Today

-2

votes

0

answers

20

views

Verifier definition of NP/poly

cc.complexity-theory complexity-classes

modified 3 hours ago Cyriac Antony 999

1

vote

1

answer

37

views

Fast private computation of dot product

cr.crypto-security privacy

modified 2 hours ago D.W. 9,333

-2

votes

0

answers

25

views

Relationship between language and circuit upper bounds [closed]

cc.complexity-theory circuit-complexity boolean-functions upper-bounds circuits

asked 12 hours ago haggisman18 1

3

votes

1

answer

30

views

Generating hard satisfiability problems with given constraint graph

graph-theory sat phase-transition random-k-sat max2sat

answered 3 hours ago Whosyourjay 453

-2

votes

0

answers

20

views

Maximal alpha beta pruning [closed]

graph-theory graph-algorithms

asked 20 hours ago Mueller 1

-1

votes

0

answers

37

views

VC-dimension of a ball [closed]

reference-request machine-learning cg.comp-geom lg.learning vc-dimension

modified 21 hours ago amit 1

0

votes

1

answer

28

views

VC-dimension of infinite set of triangle wave

reference-request machine-learning cg.comp-geom lg.learning vc-dimension

answered 22 hours ago Aryeh 8,639

-2

votes

0

answers

33

views

Quantum circuit to implement matrix multiplication

quantum-computing linear-algebra matrices quantum-information matrix-product

asked yesterday Karakoottil Dasan 5

-2

votes

0

answers

47

views

Why does the ball growing procedure of Even etal [1998] not work for directed multicut?

graph-theory graph-algorithms approximation-algorithms directed-acyclic-graph

modified 9 hours ago user122938 17

5

votes

0

answers

68

views

Are all computational models of quantum computing equivalent?

cc.complexity-theory quantum-computing

asked yesterday SagarM 449

8

votes

0

answers

149

views

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

cc.complexity-theory ds.algorithms sat exp-time-algorithms

modified 54 mins ago Giorgio Camerani 6,449

-1

votes

0

answers

47

views

Do connection and message coexist in CSP / Pi calculus?

concurrency pi-calculus

asked 2 days ago Tim 530

1

vote

0

answers

74

views

Schönhage-Strassen algorithm: why don't we work over $\mathbb{C}$

time-complexity

asked Nov 23 at 9:34 Jarne Renders 111

0

votes

0

answers

65

views

Is the traveling salesman problem still NP-hard if all edges need to be covered as well?

cc.complexity-theory np-hardness tsp

asked Nov 23 at 7:15 Sebastian Schmidt 1

-2

votes

1

answer

48

views

Finding a greedy ordering criteria

partial-order greedy-algorithms

answered 2 days ago Chip Bell 1

1

vote

1

answer

50

views

A k-approximation to k-way number partitioning

approximation-algorithms partition-problem

answered yesterday Erel Segal-Halevi 1,558

4

votes

0

answers

94

views

Time complexity for a variant of edit distance

ds.algorithms edit-distance

modified Nov 23 at 9:24 Marzio De Biasi 21.6k

6

votes

1

answer

168

views

Why does Dinur's proof of the PCP theorem fail to work for unique games?

cc.complexity-theory np-hardness approximation-hardness pcp unique-games-conjecture

answered Nov 20 at 22:10 Or Meir 4,900

0

votes

1

answer

47

views

How hard is deciding the existence of a polygonization with prescribed perimeter?

cc.complexity-theory np-hardness cg.comp-geom polygon

answered Nov 21 at 18:17 Gamow 5,437

2

votes

0

answers

88

views

$k$-XOR collision free families

ds.algorithms co.combinatorics combinatorics extremal-combinatorics

modified Nov 21 at 0:12 R B 9,176

8

votes

0

answers

105

views

Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?

graph-algorithms np-complete graph-colouring complexity

modified Nov 20 at 17:31 Christian Komusiewicz 1,647

1

vote

0

answers

64

views

Request for an update on a discussion about coinductive types in HoTT (or anywhere else)

reference-request type-theory homotopy-type-theory inductive-type

modified Nov 20 at 13:55 მამუკა ჯიბლაძე 111

7

votes

1

answer

279

views

Is solving the following system of boolean equations NP-hard?

np-hardness sat reductions

modified Nov 18 at 16:40 Joshua Grochow 33.5k

1

vote

0

answers

28

views

Damerau–Levenshtein distance with transposition of non-adjacent characters?

co.combinatorics it.information-theory coding-theory edit-distance

asked Nov 20 at 14:42 Ted 11

1

vote

1

answer

62

views

What's the intuition behind Rademacher complexity?

machine-learning

modified Nov 18 at 14:04 Aryeh 8,639

14

votes

1

answer

723

views

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

cc.complexity-theory time-complexity lower-bounds turing-machines machine-models

modified Nov 19 at 19:38 Ryan Williams 25.2k

1

vote

0

answers

57

views

Difference between a lossy encoder and a noisy channel in Information Theory

it.information-theory

modified yesterday Fred Guth 133

1

vote

0

answers

67

views

Iterated Parity Complexity

complexity logspace circuits parity

modified Nov 19 at 12:38 AnonTCS 11

0

votes

0

answers

31

views

Combinatorial object for a rational generating function

co.combinatorics

asked Nov 18 at 21:00 NietzscheanAI 743

-1

votes

0

answers

19

views

Subset selection with maximum sum and minimum variance? [closed]

co.combinatorics np-hardness optimization subset-sum

asked Nov 19 at 14:20 sumanyu muku 1

13

votes

1

answer

590

views

Computability and continuity

computability decidability

modified Nov 11 at 3:14 causative 233

-2

votes

0

answers

14

views

proving that a problem is in P [migrated]

np p-vs-np complexity

modified Nov 19 at 23:59 MikeChav 1

-3

votes

0

answers

22

views

LTL Translation of given wff [closed]

linear-temporal-logic

asked Nov 18 at 15:16 looking for logic 1

0

votes

1

answer

71

views

How many more colours do you need if you add to $G$ a maximum matching from $G^c$?

graph-theory graph-colouring

answered Nov 16 at 19:13 J.G 645

2

votes

0

answers

50

views

Can we always find a graph with a given algebraic connectivity?

ds.algorithms graph-theory graph-algorithms spectral-graph-theory

asked Nov 17 at 4:44 HallaSurvivor 121

3

votes

2

answers

123

views

Coloring where all colors are present in closed neighborhood of every vertex

graph-theory graph-colouring

answered Nov 14 at 15:17 Cyriac Antony 999

1

vote

0

answers

30

views

Dynamic permutation cycle data

ds.algorithms graph-theory permutations online-algorithms

asked Nov 16 at 19:43 Timothy 111

1

vote

1

answer

90

views

Linear regression as a hylomorphism

linear-algebra recursion

answered Nov 12 at 16:31 Neel Krishnaswami 30.1k

8

votes

1

answer

167

views

Is there any online lecture series that covers “Computational Complexity: A Modern Approach”?

cc.complexity-theory

modified Nov 8 at 20:23 Glorfindel 203

6

votes

1

answer

98

views

Extending cographs with product operation

reference-request graph-theory graph-classes cliquewidth

modified Nov 10 at 14:18 A. D. 71

1

vote

0

answers

41

views

What is the intuitive meaning of the weakest precondition expression $\text{wp}(S,R)$ in refinement calculus with miracles?

program-verification

modified Nov 14 at 16:24 Evan Aad 285

2

votes

0

answers

114

views

Can a tractable sequence distribution prefer satisfying to unsatisfying assignments?

sat pr.probability

modified Nov 10 at 18:30 D.W. 9,333

0

votes

0

answers

16

views

FASTA algorithm - how should the diagonal runs be combined?

bioinformatics

asked Nov 14 at 22:59 Supercat 9

0

votes

0

answers

43

views

How and How fast can we infer a logical formula that expresses a given graph in C$^2$( logic with 2 vars and counting quantifiers)?

cc.complexity-theory graph-theory first-order-logic

asked Nov 10 at 18:14 SagarM 449

6

votes

0

answers

300

views

On an unsubstantiated number in a proof of a weaker PCP theorem

cc.complexity-theory

modified Nov 5 at 20:10 A.2 387

0

votes

0

answers

36

views

Computing specific information of a signal propagation instead of entire signal

information

modified Nov 11 at 7:03 Paddy 121

0

votes

0

answers

61

views

An extension to the student/college admissions Gale-Shapley algorithm

ds.algorithms

asked Nov 9 at 11:49 RDavey 101

0

votes

0

answers

42

views

generalizations of hidden subgroup problem

cc.complexity-theory quantum-computing algebra hiddensubgroupproblem

asked Nov 10 at 10:31 Root 295

Top Questions

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