Theoretical Computer Science

Teacher

 Teacher
Answer a question with score of 1 or more.
Awarded 2573 times.
Known Variant of Set Cover?
Awarded Dec 3 at 13:47
Is Descriptive Complexity dead?
Awarded Nov 30 at 10:51
(post deleted or otherwise unavailable)
Awarded Nov 24 at 22:42
The Complexity of Multi-Objective Optimization
Awarded Nov 20 at 22:56
Balanced set coloring
Awarded Nov 19 at 16:49
Do we currently know a polynomial-size Frege proof for Tseitin formulas?
Awarded Nov 10 at 6:27
Generate TSP instances with known optimal
Awarded Oct 29 at 3:40
Self Referential Undecidability Construed as Incorrect Questions
Awarded Oct 19 at 14:41
Assignment problem for forming pairs of real numbers
Awarded Oct 18 at 17:51
Recent advances in computer science since 2010?
Awarded Sep 25 at 18:11
Recent advances in computer science since 2010?
Awarded Sep 24 at 4:36
What is the smallest Turing machine where it is unknown if it halts or not?
Awarded Sep 18 at 0:15
How do you achieve linear time complexity of greedy graph coloring?
Awarded Sep 13 at 12:55
Definition of a prefix-free Turing machine
Awarded Aug 21 at 22:55
Formalization of matching logic (logic behind K Framework)
Awarded Aug 18 at 10:57
Formalization of matching logic (logic behind K Framework)
Awarded Aug 15 at 11:42
Running time analysis of problems with a variable in problem definition
Awarded Aug 14 at 6:36
Can the initial algebra of a 2-variable polynomial functor be computed on the diagonal?
Awarded Aug 8 at 12:20
What are examples of recent relatively simple 'toolbox algorithms'?
Awarded Aug 7 at 20:50
What are examples of recent relatively simple 'toolbox algorithms'?
Awarded Aug 7 at 20:50
Is there a history-independent rope data structure?
Awarded Aug 6 at 16:09
Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?
Awarded Aug 6 at 9:57
Transitive reduction not provably minimal
Awarded Jul 24 at 17:43
Information Bottleneck - Calculating the Mutual information between the Labels and the Features
Awarded Jul 21 at 20:06
Approximative counting of matchings in a graph
Awarded Jul 20 at 8:25
Is $a^m b^n$ where $m - n \sqrt{2} \ge 0$ context-free?
Awarded Jul 18 at 5:04
Algorithm for comparing list elements backwards
Awarded Jul 13 at 21:08
NP-complete decision problems on deterministic automata
Awarded Jul 6 at 14:36
How hard is Hex from a symmetric position?
Awarded Jun 30 at 4:02
Formal differences between emulation and simulation?
Awarded Jun 16 at 0:17
Notation problem
Awarded Jun 1 at 21:25
Test set and benchmarks for linear programming
Awarded May 28 at 16:43
factoring large numbers
Awarded May 28 at 16:43
Can I define nested mutually dependent types in Coq?
Awarded May 13 at 19:42
Efficient algorithm/ implementation to compute Transitive Closure of a Rule with respect to a Relationship
Awarded May 9 at 15:15
Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?
Awarded Apr 28 at 14:25
Resumption-based IO systems?
Awarded Apr 26 at 8:48
Direct Proof that the Pigeonhole Principle is Hard for Regular Resolution
Awarded Apr 20 at 19:42
Why is SVP not in coNP if Gram Schmidt Orthogonalization can provide us with a lower bound of the shortest vector
Awarded Apr 19 at 2:50
What's the difference between an invariant and an "inductive" invariant?
Awarded Apr 16 at 5:05
Can an unrestricted grammar have a rule with only terminals on the left-hand side?
Awarded Apr 15 at 13:49
Complexity of Finding the Eigendecomposition of a Matrix
Awarded Apr 15 at 5:58
What are the #P-complete subfamilies of #2-SAT?
Awarded Apr 14 at 10:16
doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing
Awarded Apr 13 at 2:50
Why isn't the proof obtained using Buss's proof of the derivational completeness of LK anchored?
Awarded Apr 10 at 6:55
$DTIME_1(o(n^2))\setminus$ REGULAR
Awarded Apr 8 at 22:05
Planted Clique in G(n,p), varying p
Awarded Apr 1 at 15:05
What's the relation between applicative bisimulation and context equivalence in the $\lambda$-calculus?
Awarded Mar 30 at 8:27
(post deleted or otherwise unavailable)
Awarded Mar 27 at 23:20
Yet another constructive (Coq) proof that `nat -> nat -> nat` is not bijective. How to explain it to myself?
Awarded Mar 24 at 19:19
What are some algorithms where space complexity tends to be the limiting factor in practice?
Awarded Mar 19 at 4:09
Theoretical Computer Science vs other Sciences?
Awarded Mar 16 at 12:06
Theoretical Computer Science vs other Sciences?
Awarded Mar 16 at 12:06
Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?
Awarded Mar 14 at 22:32
Theoretical Computer Science vs other Sciences?
Awarded Mar 14 at 17:04
Theoretical Computer Science vs other Sciences?
Awarded Mar 14 at 10:03
Turing Machines and Logic
Awarded Mar 11 at 22:40
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
Awarded Mar 10 at 10:17
Does this game terminate?
Awarded Mar 7 at 6:57
Defining regular language classes with disjoint union
Awarded Feb 28 at 14:21
1
2 3 4 5
…
43

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.