Hottest Questions Today

1

vote

0

answers

43

views

Take a natural quotient of context-free grammars

fl.formal-languages context-free

asked 16 hours ago naloa 41

2

votes

0

answers

186

views

The implication of $ S(SAT)=2^{\Omega{(n)}} $ Conjecture (5.7 in Wigderson Book)

cc.complexity-theory

modified 3 hours ago Fares 21

3

votes

0

answers

51

views

Useful notion of ambiguous growing context-sensitive language

cc.complexity-theory fl.formal-languages grammars

asked yesterday naloa 41

3

votes

3

answers

167

views

Proving proof system properties within the proof system itself?

proofs proof-theory

answered 2 days ago Emil Jeřábek 13k

-3

votes

0

answers

44

views

Reduction of CNF-SAT to 3-dominating set [closed]

cc.complexity-theory

modified 2 days ago Kazi Siddiqui 1

2

votes

0

answers

60

views

SVM perturbation bounds

convex-optimization svm

modified 2 days ago Aryeh 9,088

16

votes

4

answers

3k

views

Algorithms Careers

ds.algorithms soft-question career

modified Apr 28 at 3:57 Matthieu Latapy 533

-1

votes

1

answer

112

views

What are the known classes of undirected graphs such that every graph belonging to that class is guaranteed to have a Hamiltonian Path?

graph-theory hamiltonian-paths graph-classes

answered May 3 at 13:39 GMB 2,043

2

votes

2

answers

153

views

Are there strongly normalizing lambda terms that cannot be given a System F type?

lambda-calculus typed-lambda-calculus

answered May 2 at 21:29 Damiano Mazza 4,393

-3

votes

0

answers

38

views

Proving that complement of L={ww|w belongs to {0,1}*} is CFL [closed]

automata-theory context-free

asked May 3 at 11:33 raaj 1

3

votes

2

answers

316

views

Proving not NP-complete by non-existence of gadget

np-hardness reductions

answered Apr 30 at 16:00 Joshua Grochow 34.3k

3

votes

0

answers

144

views

HyperLogLog: Why “Hyper?”

ds.data-structures terminology

asked May 1 at 20:39 templatetypedef 1,831

-2

votes

1

answer

81

views

upper bound on the total number of fixed-length paths in an acyclic graph [closed]

graph-theory

modified May 2 at 0:06 Avi Tal 1,436

3

votes

1

answer

121

views

Are uniqueness rules converse to introduction rules?

type-theory

modified Apr 29 at 11:11 ice1000 155

1

vote

1

answer

62

views

Covering a binary relation as a union of rectangles

np-hardness co.combinatorics set-cover bipartite-graphs covering-problems

answered Apr 30 at 5:13 Chris Culter 121

4

votes

1

answer

136

views

Does such a bipartite graph exist?

graph-theory graph-algorithms co.combinatorics

answered Apr 27 at 15:40 Neal Young 6,703

-1

votes

2

answers

56

views

Pi-type over a list in dependent type theory

type-theory dependent-type agda

answered Apr 29 at 12:39 ice1000 155

0

votes

0

answers

45

views

Dynamic programming algorithm to find a colorful subset of disjoint sets

parameterized-complexity fixed-parameter-tractable dynamic-programming

asked Apr 29 at 20:15 Community♦ 1

2

votes

1

answer

35

views

Relative error estimation of a special type of GapP function

cc.complexity-theory complexity-classes counting-complexity complexity

answered Apr 29 at 7:28 Emil Jeřábek 13k

0

votes

0

answers

49

views

Efficiently checking if removing a vertex yields a connected partition

graph-algorithms partition-problem

modified Apr 29 at 7:32 Benjamin Christoffersen 109

-2

votes

1

answer

108

views

Where, if any, is there currently any research being done on the subject of ternary computers? [closed]

computability

modified Apr 27 at 17:48 Jake 192

-3

votes

0

answers

114

views

Are space and time hierarchies infitesimally graded?

cc.complexity-theory hierarchy-theorems

modified Apr 27 at 5:50 1.. 11.6k

0

votes

1

answer

77

views

Reference for context-free grammar for Martin-Löf type theory

reference-request fl.formal-languages type-theory context-free

answered Apr 26 at 13:16 Neel Krishnaswami 30.6k

3

votes

1

answer

91

views

Hardness when restricted to an infinite number of far apart instance sizes

cc.complexity-theory reference-request

answered Apr 26 at 10:05 neinoa 11

1

vote

0

answers

44

views

sophistication or logical depth to detect intelligent extra-terrestrial species

reference-request it.information-theory kolmogorov-complexity ai.artificial-intel

asked Apr 27 at 18:35 dorikolmo 11

0

votes

0

answers

31

views

program search with optimization methods for (resource bounded) Kolmogorov complexity

reference-request optimization kolmogorov-complexity convex-optimization

modified Apr 28 at 8:43 dorikolmo 11

4

votes

0

answers

147

views

What kind of research can be considered publishable for undergraduate or graduate students (MSc level)

soft-question cr.crypto-security advice-request career

asked Apr 24 at 22:59 h4lius 41

3

votes

0

answers

54

views

Using Baire Category to analyze the efficiency of the Simplex Method

linear-programming topology simplex

asked Apr 26 at 16:03 Weirui.L 31

-1

votes

0

answers

32

views

k packing problem

graph-colouring derandomization fixed-parameter-tractable packing

asked Apr 27 at 12:19 jsitesting 1

0

votes

0

answers

74

views

Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$

cc.complexity-theory co.combinatorics integer-programming combinatorics

modified Apr 25 at 13:46 Rodrigo de Azevedo 219

0

votes

0

answers

160

views

Understanding a conference reviewer comment

paper-review conferences

asked Apr 23 at 18:21 karmanaut 953

10

votes

1

answer

697

views

Ambiguity of regular expressions

fl.formal-languages regular-expressions

modified Apr 18 at 21:15 Hermann Gruber 5,204

-3

votes

0

answers

91

views

When does complementariness imply lowness?

cc.complexity-theory complexity-classes

modified Apr 25 at 2:38 1.. 11.6k

-1

votes

0

answers

184

views

What progress has been towards $ZPL=L$?

cc.complexity-theory randomized-algorithms

modified Apr 23 at 0:53 1.. 11.6k

1

vote

1

answer

110

views

Is this a weaker or stronger form of the halting problem

halting-problem

answered Apr 22 at 3:14 William Hoza 1,723

0

votes

0

answers

177

views

An $O(n^2\log^c{n})$ algorithm for matrix multiplication in this paper?

cc.complexity-theory matrix-product

asked Apr 22 at 9:50 Mengfan Ma 431

3

votes

1

answer

233

views

Proof and computational complexity

cc.complexity-theory reference-request lo.logic computability

modified Apr 17 at 21:07 Denis 6,910

1

vote

0

answers

84

views

Complexity of counting 3-colourings of planar bounded degree graphs

graph-theory counting-complexity planar-graphs graph-colouring bounded-degree

modified Apr 27 at 2:10 Cyriac Antony 1,305

7

votes

0

answers

127

views

Where is Yao's original proof that distinguishers imply next-bit-predictors?

reference-request ho.history-overview pseudorandomness pseudorandom-generators

modified Apr 22 at 2:05 D.W. 9,716

13

votes

0

answers

176

views

Is this problem on unambiguous finite automata NP-complete?

automata-theory np-complete

modified Apr 21 at 19:46 Max Kubierschky 1

0

votes

0

answers

71

views

Kleisli-like category for applicatives?

functional-programming ct.category-theory monad applicative

asked Apr 22 at 20:09 Julian G. 1

3

votes

0

answers

74

views

Boltzmann sampling for containers/dependent polynomials?

co.combinatorics lo.logic type-theory dependent-type sampling

asked Apr 22 at 9:24 Neel Krishnaswami 30.6k

2

votes

1

answer

186

views

Is just one W-type enough for formalizing mathematics?

type-theory dependent-type constructive-mathematics

modified May 3 at 8:15 Andrej Bauer 25.3k

6

votes

1

answer

148

views

Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

automata-theory regular-language

modified Apr 16 at 12:32 Denis 6,910

3

votes

1

answer

153

views

What are some “must-read” papers for someone getting into Quantum Cryptography?

quantum-computing cr.crypto-security quantum-information

answered Apr 20 at 18:42 user3483902 1,013

0

votes

1

answer

61

views

Why does LTL equivalence (with next oeprator) implie trace equivalence in finite transition machines?

linear-temporal-logic

answered Apr 20 at 6:05 Shaull 4,615

4

votes

1

answer

196

views

Complexity of relaxed edge colouring

cc.complexity-theory graph-theory np-hardness graph-colouring

modified Apr 13 at 13:50 Cyriac Antony 1,305

Top Questions

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