Theoretical Computer Science

Promoter

 Promoter
First bounty you offer on your own question.
Awarded 252 times.
Structural Complexity Theory References
Awarded Aug 23 at 0:20
What are the #P-complete subfamilies of #2-SAT?
Awarded May 24 at 12:41
MIP with bounded communication between provers
Awarded May 21 at 1:50
(post deleted or otherwise unavailable)
Awarded May 20 at 10:47
(post deleted or otherwise unavailable)
Awarded Apr 28 at 5:12
How to find upper bound on regret of stochastic linear bandit not pseudo-regret
Awarded Apr 14 at 22:49
Solving Grouped Weighted Job Scheduling with Release Times and Deadlines on a Single Machine with Multiple Availability Intervals
Awarded Mar 30 at 11:21
(post deleted or otherwise unavailable)
Awarded Jan 15 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 in 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
Diagonalization arguments for QMA type proof systems
Awarded May 23, 2020 at 8:07
Are there any public synchronous discussion forums (slack, discord, etc.) for TCS
Awarded May 8, 2020 at 16:35
Hardness of approximating acyclic chromatic number
Awarded Feb 22, 2020 at 9:30
NP-hard problems with very fast exponential-time algorithms
Awarded Dec 29, 2019 at 16:40
$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$
Awarded Dec 13, 2019 at 15:20
What are some examples of algorithmic applications of noncommutative rational identity testing?
Awarded Dec 2, 2019 at 17:25
Can we map this problem to subset-sum?
Awarded Jul 16, 2019 at 11:25
Run Length eXtreme encoded length
Awarded Jul 15, 2019 at 16:55
Planar Exact Cover by even-size sets
Awarded Jun 24, 2019 at 12:35
Reference request: exponential growth rates of subsequence-closed languages are integers
Awarded Mar 9, 2019 at 19:30
A partition problem in which some numbers may be cut
Awarded Feb 2, 2019 at 22:40
Is case analysis on normal forms of lambda terms sufficient to prove parametricity results?
Awarded Jan 28, 2019 at 18:30
1
2 3 4 5

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.