Hottest Questions Today

0

votes

0

answers

13

views

Is having a particular form equivalent to being computable for functions on Church numerals?

modified 4 hours ago dspyz 916

-2

votes

0

answers

24

views

Polynomial time delay and Amortized analysis

time-complexity counting-complexity

asked 20 hours ago zhukui bai 15

2

votes

0

answers

44

views

Online detailed tutorials about Komogorov Complexity

kolmogorov-complexity online-learning

asked yesterday Dudley Brooks 21

4

votes

1

answer

101

views

Reference for automatically deriving dynamic programming algorithms from recursive algorithms?

reference-request dynamic-programming recursion

answered yesterday Neel Krishnaswami 31.2k

8

votes

3

answers

423

views

What's the logical counterpart to jumps with arguments on CPS terms?

lo.logic type-theory pl.programming-languages curry-howard continuations

modified Jan 13 at 21:53 Molossus Spondee 121

3

votes

1

answer

131

views

Proof and interpretation of the No Free Lunch theorem in data privacy

pr.probability privacy

answered 2 days ago Clement C. 4,298

2

votes

0

answers

45

views

Comparative communication complexity?

reference-request communication-complexity

modified Jan 14 at 6:24 domotorp 13.5k

1

vote

0

answers

32

views

Is the following special case of multiway number partitioning NP-hard?

np-hardness time-complexity partition-problem

asked Jan 13 at 16:49 Ryoshun Oba 11

3

votes

0

answers

36

views

Circuit uniformities more restrictive than $DLOGTIME$

circuit-complexity uniformity

asked Jan 13 at 4:12 Jake 586

-2

votes

0

answers

35

views

Is it possible to find closest number to a given irrational one, which is obtained by dividing 2 numbers in a given range faster than O(n^2)?

time-complexity

asked Jan 13 at 0:03 Omegon 97

2

votes

1

answer

65

views

On cubic planar graphs with face boundaries of length divisible by 4

graph-theory co.combinatorics planar-graphs

modified Jan 13 at 7:35 Cyriac Antony 1,435

2

votes

0

answers

45

views

Summing over weighted paths optimally

reference-request graph-theory

modified Jan 12 at 17:52 Yaroslav Bulatov 4,611

1

vote

0

answers

30

views

What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?

np-hardness quantum-computing matrices

modified Jan 12 at 22:21 VenomFangs 111

5

votes

0

answers

68

views

For which type systems have normalizaton proofs been formalized?

type-theory dependent-type embeddings

modified Jan 11 at 23:36 while1fork 151

-2

votes

0

answers

29

views

How to apporach the DFA/NFA Formation of 6 characters of length [closed]

automata-theory regular-language dfa nfa

asked Jan 12 at 16:58 Yash Singhal 1

19

votes

1

answer

800

views

FOCS virtual fee $600

soft-question conferences

answered Jan 13 at 16:18 Joshua Grochow 35k

3

votes

0

answers

49

views

Expressive power of lambda-calculus with restricted application

computability lambda-calculus

modified Jan 11 at 5:11 pbaren 653

0

votes

0

answers

73

views

Computational complexity of Private Computation

cc.complexity-theory cr.crypto-security

asked Jan 10 at 15:53 Michele Amoretti 190

4

votes

0

answers

102

views

Split a string of positive numbers into substrings with decreasing totals

reference-request partition-problem dynamic-programming

modified Jan 10 at 18:07 Travis 51

9

votes

2

answers

755

views

Randomized algorithms not based on Schwartz-Zippel

cc.complexity-theory randomized-algorithms derandomization

modified Jan 4 at 13:05 Emil Jeřábek 14.1k

-1

votes

0

answers

34

views

Semantics of assert b before S - Nielsen and Nielsen Exercise 3.2

semantics books definitions

asked Jan 10 at 1:16 petals 7

2

votes

0

answers

78

views

Subtle part of seeing $C(F) \geq \chi(f)$

communication-complexity

asked Jan 8 at 21:08 user101010 161

-1

votes

0

answers

54

views

Why query complexity is said to lower bound time complexity?

quantum-computing time-complexity query-complexity

asked Jan 8 at 11:45 Bhaskar Mukhoty 1

0

votes

0

answers

40

views

Which is more expensive, structural or nominal type-checking?

type-systems type-inference

asked Jan 8 at 15:21 Corbin 243

10

votes

1

answer

473

views

Swapping arguments of variables in higher-order pattern unification

type-theory type-inference

modified Dec 29 '21 at 14:48 András Kovács 1,214

-1

votes

0

answers

41

views

Equivalence of XML queries

np-complete tree complexity query-complexity equivalence

modified Jan 8 at 11:04 mahou_2019 9

1

vote

1

answer

160

views

How to show that Color Tiles is NP-Complete

graph-theory np-hardness np-complete

modified Jan 8 at 20:29 Marzio De Biasi 22.2k

1

vote

0

answers

22

views

How to deal with the time to minimize a function in a given interval?

ds.algorithms time-complexity polynomial-time

asked Jan 8 at 8:53 Mengfan Ma 451

-1

votes

0

answers

163

views

The Riemann Hypothesis as an halting problem

nt.number-theory halting-problem

modified Jan 4 at 19:31 D.W. 10.1k

1

vote

1

answer

162

views

2-Center problem with forbidden pairs

ds.algorithms approximation-algorithms

answered Jan 4 at 14:40 Neal Young 7,598

0

votes

0

answers

32

views

Using error-correcting codes in multi-player games

reference-request coding-theory gt.game-theory interactive-proofs

asked Jan 6 at 2:40 raycosine 193

8

votes

1

answer

103

views

Validity problem of intuitionistic two-variable logic

lo.logic complexity first-order-logic intuitionistic-logic

answered Dec 29 '21 at 13:31 Emil Jeřábek 14.1k

3

votes

1

answer

150

views

What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?

reference-request linear-programming tsp integrality-gap

modified Jan 12 at 1:28 Hao S 179

1

vote

0

answers

39

views

Cycle double covers of cubic graphs using only a few cycles

reference-request graph-theory

modified Jan 4 at 7:52 Cyriac Antony 1,435

5

votes

1

answer

144

views

Alternative to LBA for recognising context-sensitive languages

automata-theory grammars space-bounded

modified Dec 29 '21 at 17:04 Hermann Gruber 5,404

0

votes

1

answer

63

views

Is a grid graph a vertex-minor of a complete graph?

ds.algorithms graph-theory graph-algorithms planar-graphs

answered Dec 29 '21 at 11:14 Laakeri 1,298

0

votes

0

answers

57

views

A fundamental question about the proof by induction in session types

type-systems proofs pi-calculus

asked Dec 31 '21 at 0:28 Coder 109

8

votes

0

answers

103

views

improved analysis of spectral gap of zigzag product?

graph-theory linear-algebra expanders

modified Dec 27 '21 at 14:27 András Salamon 18.6k

0

votes

1

answer

59

views

Deterministic communication complexity of refinement

randomized-algorithms communication-complexity

answered Dec 26 '21 at 15:40 user3209423940248 56

2

votes

0

answers

46

views

Bin packing with non-additive load functions

reference-request co.combinatorics

modified Dec 30 '21 at 12:36 Erel Segal-Halevi 1,722

1

vote

0

answers

49

views

Computational complexity of factoring univariate polynomials with positive integer coefficients

polynomials factoring

asked Dec 28 '21 at 15:01 luciano 51

10

votes

2

answers

322

views

What are the issues with a set-like interpretation of quantifiers in type theory?

type-theory type-systems set-theory

answered Dec 18 '21 at 10:46 Andrej Bauer 26.2k

-1

votes

0

answers

38

views

How to simulate this formula on computer ghaphics?

computational-geometry

asked Dec 29 '21 at 1:45 Felipe Maya Muniz 1

1

vote

0

answers

26

views

Cycle decompositions of locally linear 4-regular graphs

reference-request graph-theory co.combinatorics

modified Dec 31 '21 at 12:42 Cyriac Antony 1,435

1

vote

0

answers

41

views

Properties of half-way locally bijective homomorphisms between Eulerian orientations

graph-theory homomorphism

modified Dec 29 '21 at 14:46 Cyriac Antony 1,435

6

votes

1

answer

277

views

Complexity of optimal elimination for a planar tensor network

ds.algorithms reference-request graph-theory graph-algorithms planar-graphs

modified Jan 6 at 16:06 Yaroslav Bulatov 4,611

Top Questions

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