Hottest Questions This Month

11

votes

3

answers

356

views

Applications of sunflower lemma in theoretical computer science

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

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

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

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

2

votes

2

answers

106

views

On the coloring number of small graphs with small cliques

reference-request co.combinatorics graph-colouring extremal-combinatorics

modified Mar 4 at 8:00 smapers 375

12

votes

0

answers

273

views

What percentage of SODA papers are galactic algorithms?

soft-question big-picture application-of-theory

modified Mar 3 at 20:54 Laakeri 748

10

votes

0

answers

209

views

Does MIP* = RE algebrize?

quantum-computing interactive-proofs

asked Mar 7 at 16:07 Geoffrey Irving 2,784

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

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

3

votes

1

answer

128

views

Is there a notion of indistinguishability obfuscation for almost equivalent circuits?

obfuscation cryptography

answered Mar 8 at 21:43 Biu 123

2

votes

1

answer

96

views

What is the computational complexity of Acyclic Joins?

cc.complexity-theory db.databases relational-structures

answered Mar 7 at 9:13 holf 1,676

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

0

votes

1

answer

90

views

Diving straight into “research” versus studying broadly as an undergrad (soft question)

soft-question

answered Mar 4 at 1:15 Neal Young 5,103

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

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

-1

votes

0

answers

141

views

Timing a career switch from math to TCS [migrated]

co.combinatorics soft-question career

modified Mar 6 at 0:56 Anonymous 11

1

vote

1

answer

63

views

Analytic Number theory in TCS [closed]

soft-question big-picture nt.number-theory comp-number-theory

modified 1 hour ago Mark 411

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

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

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

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

94

views

Is PP invariant under changing its cut-off from 1/2 to another number?

cc.complexity-theory complexity-classes time-complexity

modified Mar 11 at 17:47 user138901 347

2

votes

0

answers

87

views

Complexity of a scheduling problem with a fixed left bound of jobs

cc.complexity-theory reference-request np-hardness approximation-algorithms approximation-hardness

modified Mar 5 at 23:32 Siddha 3

3

votes

0

answers

87

views

Open Problems About Nowhere-Dense Classes of Graphs

parameterized-complexity open-problem graph-classes

asked Mar 7 at 7:03 Springberg 526

2

votes

0

answers

84

views

Types as abstract interpretations

type-systems abstract-interpretation

modified Mar 26 at 23:09 Rodrigo 545

0

votes

0

answers

78

views

Are there complexity theory consequences of the collapse NEXP=EXP^NP?

cc.complexity-theory complexity-classes time-complexity

asked Mar 6 at 12:35 user138901 347

4

votes

0

answers

75

views

Rules between UIP with function extensionality and univalence

type-theory

modified yesterday Nift 187

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

0

votes

0

answers

71

views

Apredictable sets

computability

asked Mar 3 at 14:04 Ville Salo 201

-1

votes

1

answer

41

views

Example of Delaunay Triangulation where it does not minimize the maximum angle

computational-geometry delaunay-triangulation voronoi

answered Mar 11 at 2:06 JimN 1,182

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

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

-1

votes

1

answer

64

views

Time complexity for multiplying two lower triangular matrices

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

answered 9 hours ago Pranav Bisht 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

vote

0

answers

60

views

Combinatorial problems in electronics

ds.algorithms combinatorics binary-decision-diagrams

asked Mar 3 at 18:05 meolic 223

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 411

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

-2

votes

0

answers

50

views

Describing graphs in terms of subgraphs

graph-theory

asked Mar 22 at 15:19 incidental 1

0

votes

0

answers

49

views

Sample Terms in System Omega

pl.programming-languages type-theory lambda-calculus typed-lambda-calculus

asked Mar 8 at 21:13 Solomon Bothwell 109

-2

votes

0

answers

46

views

Software for SatSolver [closed]

sat software

asked Mar 24 at 8:15 user12290 199

1

vote

0

answers

45

views

Tight estimates on the Lovász and Multilinear extensions of a submodular function

optimization convex-optimization submodularity

asked Mar 6 at 21:16 MathematicsStudent1122 111

0

votes

0

answers

44

views

Can we multiply two numbers more efficiently (using binary circuits) if one of the numbers is fixed? [duplicate]

cc.complexity-theory ds.algorithms circuit-complexity

modified Mar 11 at 16:48 Ivan 1

-3

votes

0

answers

42

views

Time complexity of binary search tree construction

time-complexity

asked Mar 25 at 22:02 Jake 1

Top Questions

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