Hottest Questions Today

0

votes

0

answers

11

views

A question on First Order Model counting for finite theories using provenance type polynomials?

modified 7 hours ago SagarM 616

0

votes

0

answers

18

views

A proved computationally-irreductible function

cc.complexity-theory computability cellular-automata universal-turing-machines

asked 8 hours ago Bob 320

3

votes

1

answer

55

views

Is $UL\neq PSPACE$ known?

space-complexity hierarchy-theorems

answered 12 hours ago William Hoza 1,448

4

votes

0

answers

69

views

A variant of transfer learning

reference-request machine-learning

modified 7 hours ago Aryeh 8,921

3

votes

0

answers

64

views

Does k-Median problem become any easier when L = C?

clustering metric-spaces

modified 4 hours ago Hugo Manet 101

10

votes

1

answer

54

views

Is the exponent in the rectangular matrix multiplication convex?

ds.algorithms time-complexity matrix-product

modified 5 hours ago user2316602 409

0

votes

0

answers

30

views

Where is the following function in?

cc.complexity-theory complexity-classes

asked 16 hours ago 1.. 11.7k

1

vote

0

answers

27

views

Definition of Rabin acceptance condition for omega automatons

fl.formal-languages automata-theory omega-language

asked 23 hours ago Yekhezkel Yovel 111

0

votes

1

answer

37

views

Minimum Degree Spanning Tree Without Restricting Vertices Searched

approximation-algorithms

modified yesterday user3508551 319

0

votes

0

answers

104

views

Why do people refer to NP-complete as NP-hard? [closed]

complexity-classes

asked yesterday user2153235 109

2

votes

2

answers

83

views

Partitioning a connected polygon into connected pieces of equal area

cg.comp-geom partition-problem polygon

answered yesterday David Eppstein 49.3k

0

votes

0

answers

19

views

Given an input sequence of real numbers, how to find the closest sequence in a large set of sequences

reference-request approximation-algorithms ds.data-structures randomized-algorithms

asked 2 days ago Penelope Benenati 101

1

vote

0

answers

52

views

Consequences of an $o(\log n)$-approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem

complexity-classes approximation-hardness

asked 2 days ago Lamine 1,064

0

votes

2

answers

100

views

Minimum number of triangles required to cover a complete graph?

graph-theory covering-problems vertex-cover

answered yesterday Peter Shor 23k

1

vote

1

answer

76

views

An invariance theorem for algorithmically random data in statistical learning

reference-request machine-learning kolmogorov-complexity

modified Feb 22 at 12:23 Aidan Rocke 287

2

votes

0

answers

91

views

Understanding the Physical Church-Turing thesis and its implications

physics church-turing-thesis

modified 2 days ago Aidan Rocke 287

3

votes

1

answer

105

views

What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?

cc.complexity-theory complexity-classes lower-bounds big-picture ac0

answered Feb 22 at 3:49 Jake 159

8

votes

2

answers

169

views

Are there analogous works to PPSZ algorithm for #P?

sat counting-complexity

answered Feb 20 at 18:34 Giorgio Camerani 6,505

3

votes

0

answers

185

views

Are CCS and CSP still worth studying?

pl.programming-languages concurrency

modified 2 days ago Lev Reyzin♦ 11.5k

10

votes

1

answer

119

views

It is known that $L \subsetneq PH$?

oracles polynomial-hierarchy logspace

answered Feb 19 at 14:16 Ryan Williams 25.7k

1

vote

0

answers

69

views

On the equivalence of incompressibility and incompleteness in machine learning

machine-learning it.information-theory kolmogorov-complexity

modified Feb 21 at 12:25 Aidan Rocke 287

3

votes

1

answer

97

views

A stronger Flow Decomposition Theorem?

graph-theory graph-algorithms network-modeling flow-problems

modified Feb 21 at 11:15 Kristoffer Arnsfelt Hansen 3,960

-2

votes

0

answers

47

views

Unambiguous bipartite ustcon and stcon

cc.complexity-theory logspace

modified Feb 21 at 0:25 1.. 11.7k

9

votes

1

answer

177

views

Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

cc.complexity-theory ds.algorithms graph-algorithms time-complexity nondeterminism

modified Feb 19 at 19:22 Michael Wehar 4,703

2

votes

1

answer

38

views

Problem conditions to use Laplacian solvers

graph-theory graph-algorithms linear-algebra matrices sparse-matrix

modified Feb 20 at 15:32 Mah 123

32

votes

12

answers

5k

views

Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

cc.complexity-theory ho.history-overview exp-time-algorithms

answered Jan 28 at 11:50 Joe Boy 101

4

votes

1

answer

119

views

Is $GCT$ necessarily a negative result program?

cc.complexity-theory ds.algorithms big-picture algebraic-complexity symmetry

answered Feb 19 at 4:16 Joshua Grochow 34.1k

-2

votes

1

answer

29

views

Can there be a graph where IDDFS vists fewer nodes than BFS [closed]

graph-theory search-problem

answered Feb 21 at 11:31 Hugo Manet 101

-2

votes

0

answers

118

views

Is “paradigm” a word with meaning in syntax or semantics of programming languages? [closed]

computability pl.programming-languages functional-programming concurrency logic-programming

modified Feb 18 at 18:17 Tim 634

1

vote

1

answer

132

views

Pursuing Theoretical Computer Science after CS major

cc.complexity-theory quantum-computing

modified Feb 18 at 16:19 Brandon Miles 3

1

vote

0

answers

99

views

What is the difference between a model of computation and a programming language?

computability pl.programming-languages concurrency universal-computation

asked Feb 17 at 18:21 Tim 634

-1

votes

0

answers

49

views

What are terms to call pieces in syntax and in semantics in a programming language? [closed]

pl.programming-languages terminology semantics

asked Feb 18 at 13:23 Tim 634

-1

votes

0

answers

44

views

On known Space time bounds and $\mathsf{Logtime}$ uniformity?

cc.complexity-theory sat lower-bounds logspace space-time-tradeoff

asked Feb 18 at 14:04 1.. 11.7k

-1

votes

0

answers

48

views

Space Time Lower Bounds for $\#SAT$?

lower-bounds space-time-tradeoff

modified Feb 18 at 10:35 1.. 11.7k

0

votes

1

answer

53

views

What would be the performance properties of a comb or shell sort where the gap sequence is the prime numbers?

sorting

answered Feb 18 at 23:02 Simply Beautiful Art 111

0

votes

0

answers

65

views

On Determinant modulo $2^k$ complexity

complexity-classes determinant

asked Feb 17 at 23:27 1.. 11.7k

1

vote

0

answers

21

views

Pagerank update upon vertex removal

graph-algorithms markov-chains streaming-algorithms probabilistic-computation

asked Feb 19 at 9:04 Matthieu Latapy 281

1

vote

0

answers

69

views

Algorithms for finding unique solutions of NP-complete problems

cc.complexity-theory search-problem unique-solution

modified Feb 17 at 19:35 Mohammad Al-Turkistany 20.2k

0

votes

0

answers

24

views

Looking for information about a problem of a least subset of vectors modulo 2 summing to another vector [duplicate]

time-complexity linear-algebra finite-fields

asked Feb 19 at 1:04 Maja Trela 1

-2

votes

0

answers

44

views

$\mathsf{NP}$-complete reduction efficiency and $\mathsf{NP}$-completeness of subexponential subsets of $\mathsf{NP}$ complete problems

cc.complexity-theory complexity-classes boolean-functions reductions np-complete

modified Feb 17 at 15:30 1.. 11.7k

2

votes

1

answer

52

views

random sampling DAGs via nilpotent matrix sampling

graph-theory directed-acyclic-graph

answered Feb 20 at 12:28 thibo 131

-2

votes

1

answer

75

views

Set cover with small subsets [closed]

np-hardness set-cover

answered Feb 15 at 6:31 user3209423940248 206

4

votes

0

answers

136

views

The graph of problem reductions

cc.complexity-theory complexity-classes soft-question reductions big-list

modified Feb 14 at 21:31 Matthieu Latapy 281

0

votes

0

answers

58

views

Asymptotically sub-optimal but provably optimal algorithms in a finite range for NP-Hard problems?

sat

modified Feb 15 at 18:35 SagarM 616

-1

votes

0

answers

54

views

How is a divide and conquer recursive algorithm represented in the actor model with lambda calculus?

pl.programming-languages lambda-calculus concurrency recursion

modified Feb 15 at 14:35 Tim 634

Top Questions

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