Theoretical Computer Science Stack Exchange

3

votes

2

answers

105

views

Complexity of Set Difference

ds.algorithms ds.data-structures time-complexity

answered 5 hours ago Mahdi Cheraghchi 3,619

3

votes

2

answers

81

views

3-colourability of Eulerian maximal planar graph

graph-theory planar-graphs graph-colouring

modified 19 hours ago Cyriac Antony 788

1

vote

2

answers

85

views

Embedding a n-tree into a b-dimensional space

optimization computational-geometry

answered yesterday jackb 173

0

votes

0

answers

51

views

Time complexity of Succinct-CVP

time-complexity lower-bounds exp-time-algorithms succinct

modified yesterday Mohsen Ghorbani 225

1

vote

2

answers

716

views

Does this notation have a special meaning?

graph-theory

answered 2 days ago Sarkar B 1

5

votes

1

answer

77

views

Complexity of approximating a real function using queries

reference-request complexity-classes approximation-algorithms query-complexity computing-over-reals

answered 2 days ago Aryeh 8,210

578

votes

6

answers

117k

views

+50

What's new in purely functional data structures since Okasaki?

reference-request big-list ds.data-structures functional-programming

modified Jul 16 at 22:57 dmbarbour 81

22

votes

2

answers

789

views

PPAD and Quantum

cc.complexity-theory complexity-classes quantum-computing cr.crypto-security nash-equilibrium

modified Jul 16 at 21:29 Geoffroy Couteau 748

1

vote

0

answers

36

views

Practical Data-oblivious Compaction?

sorting-network cache-oblivious

asked Jul 16 at 20:16 Mark 508

3

votes

1

answer

80

views

Parametrized complexity of sparse optimization

np-hardness optimization convex-optimization

answered Jul 15 at 21:33 Mahdi Cheraghchi 3,619

10

votes

1

answer

118

views

Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?

reference-request lo.logic computability

answered Jul 15 at 18:12 Noah Schweber 250

-2

votes

0

answers

88

views

Is it new that no single-tape Turing Machine can compute loglog n in time o(n log n)?

cc.complexity-theory time-complexity

asked Jul 15 at 9:01 xxmmjj 1

Jun	JUL	Aug
	20
2019	2020	2021

Stack Exchange Network

current community

your communities

more stack exchange communities

Explore our Questions

Complexity of Set Difference

3-colourability of Eulerian maximal planar graph

Embedding a n-tree into a b-dimensional space

Time complexity of Succinct-CVP

Does this notation have a special meaning?

Complexity of approximating a real function using queries

What's new in purely functional data structures since Okasaki?

PPAD and Quantum

Practical Data-oblivious Compaction?

Parametrized complexity of sparse optimization

Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?

Is it new that no single-tape Turing Machine can compute loglog n in time o(n log n)?

Hot Network Questions