Hottest Questions Today

0

votes

1

answer

58

views

Analytic Number theory in TCS [closed]

modified 42 mins ago Mark 401

-2

votes

0

answers

25

views

3SAT to 3,{3,4} SAT

sat

modified 12 hours ago codor 1

-1

votes

1

answer

64

views

Time complexity for multiplying two lower triangular matrices

cc.complexity-theory ds.algorithms time-complexity matrices recursion

answered 8 hours ago Pranav Bisht 1

-2

votes

0

answers

32

views

Is Safe AI undecideable? [closed]

ai.artificial-intel

asked 23 hours ago user57461 1

4

votes

0

answers

75

views

Rules between UIP with function extensionality and univalence

type-theory

modified yesterday Nift 187

4

votes

0

answers

67

views

Optimal point placement on integer lattice

ds.algorithms optimization ds.data-structures computational-geometry voronoi

modified yesterday user56067 41

-2

votes

0

answers

20

views

Why exactly can real valued time sequences be replaced with rational valued timed sequences?

automata-theory

asked 2 days ago Lennert Geebelen 1

11

votes

3

answers

355

views

Applications of sunflower lemma in theoretical computer science

cc.complexity-theory co.combinatorics set-system

modified Mar 29 at 20:48 Emil Jeřábek 11.4k

1

vote

1

answer

59

views

Reference request: Depth- (or Breadth-) first search with hints?

graph-theory graph-algorithms

answered Mar 29 at 5:57 Mark 401

2

votes

0

answers

27

views

What is the minimal class of subshifts for which conjugacy is known to be undecidable?

automata-theory undecidability cellular-automata

modified Mar 29 at 14:36 Shaull 3,961

8

votes

1

answer

173

views

The theoretical complexity of Go - The state of the art

complexity-classes gt.game-theory complexity

modified Mar 26 at 11:22 Denis 6,182

6

votes

0

answers

78

views

Subgraph isomorphism on graph sequences

ds.algorithms reference-request graph-algorithms graph-isomorphism parameterized-complexity

modified Mar 27 at 9:33 LeechLattice 183

-1

votes

0

answers

38

views

Notation of sequences in rate distortion theory

it.information-theory coding-theory st.statistics

modified Mar 26 at 16:21 sn3jd3r 99

-3

votes

0

answers

42

views

Time complexity of binary search tree construction

time-complexity

asked Mar 25 at 22:02 Jake 1

2

votes

0

answers

99

views

Proof systems induced by NP-complete problems

cc.complexity-theory reference-request proof-complexity

modified Mar 24 at 17:13 Mohammad Al-Turkistany 19.6k

-2

votes

0

answers

37

views

Channel Coding theorem (Code Symmetry)

it.information-theory

asked Mar 25 at 19:44 Diogo Landau 1

1

vote

0

answers

38

views

Relation between automorphism group of a linear code and its dual code

coding-theory algebra gr.group-theory combinatorics

asked Mar 25 at 16:21 Root 143

7

votes

5

answers

337

views

NP-complete decision problems on deterministic automata

cc.complexity-theory np-hardness fl.formal-languages automata-theory np-complete

modified Mar 24 at 21:25 Hermann Gruber 4,359

3

votes

1

answer

131

views

Areas of research and open problems in functional programming [closed]

pl.programming-languages functional-programming open-problem research-practice haskell

answered Mar 23 at 13:57 xrq 963

2

votes

0

answers

84

views

Types as abstract interpretations

type-systems abstract-interpretation

modified Mar 26 at 23:09 Rodrigo 545

4

votes

1

answer

382

views

Church-style CoC with axiom for induction over Church-encoded unit, is it consistent?

type-theory calculus-of-constructions

answered Mar 19 at 13:54 Neel Krishnaswami 29.7k

-2

votes

0

answers

46

views

Software for SatSolver [closed]

sat software

asked Mar 24 at 8:15 user12290 199

7

votes

1

answer

307

views

Technical lemma about curves used in original proof of PCP theorem

cc.complexity-theory algebra pcp

modified Mar 20 at 21:49 A.2 331

0

votes

0

answers

52

views

Does the underlying computational calculus in type theories affect decidability? [closed]

type-theory lambda-calculus type-systems type-inference curry-howard

asked Mar 23 at 11:39 Bharat Khatri 127

0

votes

0

answers

23

views

Best known bounds on feedback arcset in high-girth directed graphs?

ds.algorithms graph-theory directed-acyclic-graph combinatorics

asked Mar 24 at 3:55 Arun Jambulapati 1

-2

votes

0

answers

50

views

Describing graphs in terms of subgraphs

graph-theory

asked Mar 22 at 15:19 incidental 1

2

votes

0

answers

62

views

Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? // Quantum automata

fl.formal-languages quantum-computing automata-theory

asked Mar 21 at 18:28 catalyst 21

-1

votes

0

answers

22

views

Evolving expression trees to approximate an unknown function

ds.algorithms approximation-algorithms randomized-algorithms tree ne.neural-evol

asked Mar 22 at 20:05 void 99

6

votes

0

answers

80

views

Programmatic higher inductive/inductive-inductive types with equalities between equalities

reference-request type-systems application-of-theory homotopy-type-theory inductive-type

asked Mar 18 at 18:07 Nift 187

5

votes

0

answers

127

views

What research is being done in classical complexity theory?

cc.complexity-theory soft-question

asked Mar 17 at 16:44 exfret 593

5

votes

0

answers

110

views

Program size versus program running time

soft-question time-complexity

modified Mar 17 at 23:15 Marzio De Biasi 21.2k

3

votes

1

answer

116

views

Binary search on coin heads probability

pr.probability randomized-algorithms st.statistics

answered Mar 15 at 22:06 Clement C. 3,684

0

votes

1

answer

74

views

Optimization problems with same optimal value, but different approximation behavior

approximation-hardness approximation

answered Mar 15 at 12:00 Jukka Suomela 10.8k

1

vote

0

answers

64

views

Explicit binary codes with block length n, distance n / log n, rate 1 - o(1)?

coding-theory

asked Mar 18 at 2:07 William Hoza 1,276

-2

votes

0

answers

39

views

performance vs complexity given an optimization problem

cc.complexity-theory complexity-classes

asked Mar 18 at 18:26 Deniz Sargun 1

13

votes

1

answer

282

views

Universal Boolean Formulas

circuit-complexity universal-computation boolean-formulas

modified yesterday Sasha Kozachinskiy 498

1

vote

1

answer

62

views

Running an algorithm for fixed amount of time on RAM model machine

ds.algorithms time-complexity machine-models formal-methods

answered Mar 14 at 4:37 D.W. 8,963

1

vote

1

answer

204

views

Quantum Computing: project ideas

quantum-computing quantum-information

modified 2 days ago Community♦ 1

4

votes

1

answer

114

views

Is $L \subset 1NL$ when $L \neq NL$?

cc.complexity-theory complexity-classes turing-machines nondeterminism space-complexity

answered Mar 9 at 10:17 domotorp 12.7k

0

votes

2

answers

103

views

Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials? [closed]

cc.complexity-theory np-hardness complexity-classes

modified Mar 9 at 16:22 Emil Jeřábek 11.4k

2

votes

0

answers

72

views

Variation of edge-disjoint spanning trees

graph-theory graph-algorithms search-problem spanning-tree

modified Mar 12 at 23:22 Yuliang Li 21

Top Questions

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