Theoretical Computer Science

Announcer

 Announcer
Share a link to a post later visited by 25 unique IP addresses. This badge can be awarded multiple times.
Awarded 590 times.
Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?
Awarded Mar 17 at 19:34
Yet another constructive (Coq) proof that `nat -> nat -> nat` is not bijective. How to explain it to myself?
Awarded Mar 11 at 13:50
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
Awarded Mar 10 at 21:10
Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?
Awarded Feb 16 at 15:40
Reading up on $BQP = BPP^{BQNC}$
Awarded Feb 13 at 21:28
Number of distinct nodes in a random walk
Awarded Jan 26 at 8:18
Does LOGLOG = NLOGLOG?
Awarded Jan 26 at 2:08
Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?
Awarded Jan 25 at 10:57
Truly random number generator: Turing computable?
Awarded Jan 12 at 7:31
Approximation algorithms for Metric TSP
Awarded Jan 11 at 11:43
Best Upper Bounds on SAT
Awarded Jan 10 at 18:27
Problem in BPP but not known to be in RP or co-RP
Awarded Jan 10 at 12:51
Ambiguity in regular and context-free languages
Awarded Jan 9 at 13:45
When a process spawns another process
Awarded Dec 19, 2022 at 1:31
Funny TCS-related papers etc?
Awarded Dec 16, 2022 at 16:31
An extension of Chernoff bound
Awarded Dec 16, 2022 at 11:56
What is the difference between a second preimage attack and a collision attack?
Awarded Dec 16, 2022 at 8:32
How to find interesting research problems
Awarded Dec 3, 2022 at 21:41
Algorithms from the Book
Awarded Dec 2, 2022 at 10:04
A special case of the boolean multivariate quadratic polynomial problem
Awarded Nov 18, 2022 at 5:42
Distinguishing between two coins
Awarded Nov 17, 2022 at 7:11
Counting words accepted by a regular grammar
Awarded Nov 16, 2022 at 20:45
An intuitive/informal proof for LP Duality?
Awarded Oct 26, 2022 at 5:16
Monotone arithmetic circuit complexity of elementary symmetric polynomials?
Awarded Sep 28, 2022 at 3:48
Hardness of 3-dimensional matching variant
Awarded Sep 20, 2022 at 22:05
Separating Logspace from Polynomial time
Awarded Aug 22, 2022 at 6:46
Stratification of System Fω
Awarded Jul 30, 2022 at 12:16
What notable automaton models have polynomially-decidable containment?
Awarded Jul 29, 2022 at 10:33
Finding a minimal addition chain for a given number
Awarded Jul 16, 2022 at 12:20
Quickly finding empty-string producing nonterminals in a CFG
Awarded Jul 16, 2022 at 7:18
O(n)-space, polylog-time subtree sums in incremental forests?
Awarded Jul 14, 2022 at 3:41
Generalizing the "median trick" to higher dimensions?
Awarded Jul 7, 2022 at 18:01
An analogue of Scott continuity for infinite-time-Turing-computable functions
Awarded Jun 6, 2022 at 19:02
Is it possible to test if a computable number is rational or integer?
Awarded Jun 3, 2022 at 13:41
Is finding the minimum regular expression an NP-complete problem?
Awarded Jun 1, 2022 at 20:57
Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$
Awarded May 15, 2022 at 19:32
Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$
Awarded Apr 28, 2022 at 1:46
Looking for a nice problem inside SC but not in the first two levels
Awarded Apr 24, 2022 at 21:32
Lighting up all elements of a poset by toggling upsets
Awarded Apr 14, 2022 at 20:27
Many-one reductions vs. Turing reductions to define NPC
Awarded Apr 12, 2022 at 2:55
Induction-recursion in models other than $\mathbf{Set}$
Awarded Apr 1, 2022 at 21:05
Will Martin-Löf Type Theory lead to a greater ability to write provably correct code?
Awarded Mar 26, 2022 at 16:15
A total language that only a Turing complete language can interpret
Awarded Mar 25, 2022 at 20:41
hardness of approximating the chromatic number in graphs with bounded degree
Awarded Mar 9, 2022 at 22:40
What's new in purely functional data structures since Okasaki?
Awarded Feb 26, 2022 at 18:20
minimizing size of regular expression
Awarded Feb 19, 2022 at 13:01
An NP-complete variant of factoring.
Awarded Feb 17, 2022 at 16:18
Bounding the gap between quantum and deterministic query complexity
Awarded Jan 23, 2022 at 0:35
Difference between infinite state machines and turing machines
Awarded Jan 15, 2022 at 0:32
What are the issues with a set-like interpretation of quantifiers in type theory?
Awarded Dec 18, 2021 at 15:10
Barriers to show $P=NP$
Awarded Nov 27, 2021 at 21:42
What papers should everyone read?
Awarded Nov 23, 2021 at 13:51
What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?
Awarded Nov 17, 2021 at 0:06
How can we compute the VC dimension of a finite class of sets?
Awarded Nov 7, 2021 at 20:31
Is there an isomorphism between universal domains $\mathcal{P}\omega$ and the interval domain $\mathbf{I}\mathbb{R}$?
Awarded Nov 6, 2021 at 23:03
Is it known how much computation a fixed-point combinator gets you?
Awarded Nov 5, 2021 at 6:27
Dependent Sums and Products
Awarded Oct 29, 2021 at 14:31
How can one ACTUALLY minimize a regular expression? [closed]
Awarded Oct 27, 2021 at 16:51
How do I referee a paper?
Awarded Oct 21, 2021 at 13:42
Simple reduction to unbounded knapsack?
Awarded Oct 8, 2021 at 21:19
1
2 3 4 5
…
10

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.