Skip to main content
Theoretical Computer Science

Promoter

 Promoter
First bounty you offer on your own question.
Awarded 264 times.
Can a Queue with Fewer Serves outperform a Queue with More Servers?
Awarded Sep 5 at 12:57
Is $K^t$ complexity closed under composition
Awarded Aug 30 at 14:33
Bounds on the length of simple paths in DFAs resulting from the powerset construction of an NFA
Awarded Aug 9 at 14:17
Collapse of query and oracle hierarchies
Awarded Jul 16 at 18:26
Minimizing a submodular function containing summation and production under partition matroid constraint
Awarded Jul 4 at 1:12
Are there any programming languages based on the method of analytic tableaux, aside from Fitting's Proflog?
Awarded Jul 2 at 6:06
(post deleted or otherwise unavailable)
Awarded Jun 18 at 14:55
Comparing Shor's and Regev's Quantum Factoring algorithm
Awarded Apr 3 at 7:25
In logic programming, what would a language with second-order model theory gain?
Awarded Mar 31 at 15:36
(post deleted or otherwise unavailable)
Awarded Jan 30 at 6:55
Sparsification and critical clauses in SAT
Awarded Jan 29 at 14:07
(post deleted or otherwise unavailable)
Awarded Dec 22, 2023 at 14:47
Structural Complexity Theory References
Awarded Aug 23, 2023 at 0:20
What are the #P-complete subfamilies of #2-SAT?
Awarded May 24, 2023 at 12:41
MIP with bounded communication between provers
Awarded May 21, 2023 at 1:50
(post deleted or otherwise unavailable)
Awarded May 20, 2023 at 10:47
(post deleted or otherwise unavailable)
Awarded Apr 28, 2023 at 5:12
(post deleted or otherwise unavailable)
Awarded Apr 14, 2023 at 22:49
Solving Grouped Weighted Job Scheduling with Release Times and Deadlines on a Single Machine with Multiple Availability Intervals
Awarded Mar 30, 2023 at 11:21
(post deleted or otherwise unavailable)
Awarded Jan 15, 2023 at 12:55
What is (a reasonable conjectured lower bound on) the query complexity of solving an $n\times n$ system of linear equations given space $O(n)$?
Awarded Dec 10, 2022 at 13:50
How do separations of query complexities imply complexity class separations relative to oracles?
Awarded Dec 2, 2022 at 16:01
2xn grid graphs from ring graphs via local complementations
Awarded Oct 31, 2022 at 4:57
Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82
Awarded Sep 29, 2022 at 4:41
Natural hard communication problems with both nondeterministic and co-nondeterministic complexity of $\sqrt{n}$?
Awarded Sep 22, 2022 at 19:08
On the number of optimal prefix-free binary codes [closed]
Awarded Sep 4, 2022 at 15:27
Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)
Awarded Jul 30, 2022 at 17:25
From coin flips to algebraic functions via pushdown automata
Awarded Jul 30, 2022 at 2:51
Decomposition of a permutation into increasing subsequences
Awarded Jul 16, 2022 at 7:36
(post deleted or otherwise unavailable)
Awarded Jul 10, 2022 at 22:56
Deciding if all matrix multiplication entries have at least two witnesses
Awarded Jun 23, 2022 at 23:55
(post deleted or otherwise unavailable)
Awarded May 21, 2022 at 3:57
Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)
Awarded May 9, 2022 at 10:36
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 26, 2022 at 11:18
(post deleted or otherwise unavailable)
Awarded Apr 19, 2022 at 20:25
Semantics of logic/relational programming languages
Awarded Mar 26, 2022 at 18:57
Maximize the mutual information between 2 discrete random variables
Awarded Feb 8, 2022 at 3:47
What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?
Awarded Dec 22, 2021 at 5:57
Algorithm for finding traffic equilibrium
Awarded Dec 8, 2021 at 11:07
Do random functions have synchronous, alternating circuits with non-injective first layers?
Awarded Nov 26, 2021 at 2:12
Maximally Permissive Strategies for Safety Properties
Awarded Oct 4, 2021 at 7:50
Is there any Bi-criteria PTAS for Metric $k$-Median?
Awarded Sep 29, 2021 at 19:08
Applications of solvability in the λ-calculus
Awarded Sep 25, 2021 at 15:36
Relationship between Random Graph Theory and TCS
Awarded Aug 27, 2021 at 2:18
Input length and calculation time to simulate a quantum measurement
Awarded Aug 26, 2021 at 11:33
Problem in the paper "Stable Minimum Space Partitioning in Linear Time"
Awarded Aug 5, 2021 at 21:26
Context Free Grammar For Complement Of { www | ... } with minimal pumping length?
Awarded Jun 29, 2021 at 18:15
Theorem on non-decreasing probability of success of an algorithm
Awarded Jun 23, 2021 at 14:45
How is a "low-degree polynomial" precisely defined in Algebrization?
Awarded Jun 15, 2021 at 21:15
Computational complexity of minimum distance of rate $\frac{1}{2}$ codes
Awarded May 23, 2021 at 3:11
NP-hardness for one-dimensional facility location problem with entrance fee for each customer [closed]
Awarded Dec 29, 2020 at 8:55
Reducing Parameterized Problems (whose solution size can be "large") to W[i]-complete problems (for fixed i)
Awarded Nov 12, 2020 at 10:18
How to calculate complexity in a high dimensional space?
Awarded Oct 22, 2020 at 16:32
Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph
Awarded Oct 13, 2020 at 0:06
Is there a competitive algorithm for this online scheduling problem to minimize the truncated gaps?
Awarded Oct 12, 2020 at 8:41
Alternative exponential definition of Kolmogorov complexity
Awarded Sep 30, 2020 at 23:13
Estimating the cardinality of multisets given some sets of different sizes
Awarded Aug 29, 2020 at 4:42
Order-invariant conjunctive queries are FO-definable without the order
Awarded Aug 22, 2020 at 8:37
Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?
Awarded Jul 3, 2020 at 17:04
(post deleted or otherwise unavailable)
Awarded Jun 3, 2020 at 11:28
1
2 3 4 5