Benefactor - Badge - Theoretical Computer Science Stack Exchange

Benefactor

First bounty you manually award on your own question.

Awarded 99 times.

How do separations in of query complexities imply complexity class separations relative to oracles?

Awarded Dec 6, 2022 at 16:36

gen

2501 gold badge2 silver badges11 bronze badges

Check whether DFA accepts majority of words less than a cutoff with another DFA

Awarded Oct 8, 2022 at 22:41

Jake

1,0154 silver badges21 bronze badges

Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)

Awarded Aug 2, 2022 at 22:35

Emilio Ferrucci

858 bronze badges

Decomposition of a permutation into increasing subsequences

Awarded Jul 20, 2022 at 11:19

Vk1

1379 bronze badges

Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)

Awarded May 13, 2022 at 13:47

Marco Fellous-Asiani

936 bronze badges

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 8:16

dohmatob

2911 silver badge12 bronze badges

Algorithm for finding traffic equilibrium

Awarded Dec 11, 2021 at 18:25

Ace shinigami

675 bronze badges

Complexity of finding the most likely edge

Awarded Nov 25, 2021 at 19:27

Simd

3,94019 silver badges48 bronze badges

Is there any Bi-criteria PTAS for Metric $k$-Median?

Awarded Sep 30, 2021 at 21:25

Inuyasha Yagami

1,3611 gold badge7 silver badges24 bronze badges

Relationship between Random Graph Theory and TCS

Awarded Sep 1, 2021 at 19:41

MikeG

1136 bronze badges

What is the impact of encodings of sparse structures on the complexity of the model checking problem?

Awarded Aug 14, 2021 at 9:42

Bartosz Bednarczyk

1,1651 gold badge11 silver badges17 bronze badges

Context Free Grammar For Complement Of { www | ... } with minimal pumping length?

Awarded Jul 1, 2021 at 11:07

Henning

592 silver badges13 bronze badges

Reducing Parameterized Problems (whose solution size can be "large") to W[i]-complete problems (for fixed i)

Awarded Nov 18, 2020 at 11:31

Haden Hooyeon Lee

1578 bronze badges

Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

Awarded Oct 16, 2020 at 2:03

padawan

939 bronze badges

NP-hard problems with very fast exponential-time algorithms

Awarded Jan 1, 2020 at 0:15

vb le

4,82836 silver badges46 bronze badges

$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$

Awarded Dec 14, 2019 at 16:05

Timon Knigge

716 bronze badges

Planar Exact Cover by even-size sets

Awarded Jul 1, 2019 at 5:10

Yota Otachi

1,72115 silver badges24 bronze badges

A partition problem in which some numbers may be cut

Awarded Feb 6, 2019 at 18:45

Erel Segal-Halevi

1,8809 silver badges20 bronze badges

Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic

Awarded Jul 6, 2018 at 9:54

yters

2031 silver badge9 bronze badges

List of (unsolved) complexity problems arising from PL

Awarded Apr 17, 2018 at 1:48

xrq

1,1356 silver badges16 bronze badges

Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

Awarded Dec 11, 2017 at 3:46

mm8511

2031 silver badge8 bronze badges

Examples of quasilinear vs. essentially linear time translatable models

Awarded Nov 27, 2017 at 2:56

Dan Brumleve

5505 silver badges18 bronze badges

Bipartite matching with degree domination

Awarded Oct 4, 2017 at 2:30

Wei Zhan

7235 silver badges16 bronze badges

Pumping Lemma over 2 way Automaton

Awarded Jun 16, 2017 at 8:28

TheoryQuest1

7835 silver badges12 bronze badges

Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

Awarded May 1, 2017 at 19:37

Michael Wehar

5,0251 gold badge22 silver badges51 bronze badges

How can non-terminating $\lambda$-terms be turned into fixed-point combinators?

Awarded Mar 23, 2017 at 11:32

cody

13.4k1 gold badge45 silver badges93 bronze badges

Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

Awarded Mar 2, 2017 at 4:22

Omar Shehab

3319 silver badges21 bronze badges

A subset grouping problem

Awarded Feb 17, 2017 at 23:00

user357269

836 bronze badges

Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Awarded Jul 30, 2016 at 17:24

TomR

4093 silver badges10 bronze badges

theorems for universal set of quantum gates for SU(d)

Awarded May 13, 2016 at 17:42

user25957

636 bronze badges

NP completeness of linear $0-1$ assignment problem

Awarded Dec 12, 2015 at 20:32

Turbo

12.6k1 gold badge17 silver badges67 bronze badges

Submatrix of small rank

Awarded Nov 24, 2015 at 5:56

Kumar

2,00413 silver badges27 bronze badges

Min Hamming distance of a given string from substrings of another string

Awarded Nov 23, 2015 at 6:52

G H

11310 bronze badges

What is the application of combinatorial game theory

Awarded Aug 23, 2015 at 14:37

Halbort

1539 bronze badges

How do you encode Lamping's abstract algorithm using interaction combinators?

Awarded Aug 19, 2015 at 0:08

MaiaVictor

3,03510 silver badges30 bronze badges

Constrained version of vertex cover in a bipartite graph

Awarded Aug 18, 2015 at 3:46

Ram

6293 silver badges14 bronze badges

Enumerating set combinations in an order that maximises the number of previously unseen subsets

Awarded May 29, 2015 at 17:17

Gareth A. Lloyd

536 bronze badges

Sparser Bipartite graphs?

Awarded May 29, 2015 at 6:25

SamiD

2,29917 silver badges28 bronze badges

What functions can System F not compute?

Awarded Feb 26, 2015 at 13:20

Mike H-R

3633 silver badges9 bronze badges

How and why does Recrypt function work?

Awarded Dec 23, 2014 at 10:47

Hilder Vitor Lima Pereira

18110 bronze badges

Name a set of program variables

Awarded Nov 14, 2014 at 16:51

SoftTimur

735 bronze badges

Methods of converting an image to graph

Awarded Oct 8, 2014 at 15:58

Gigili

1331 silver badge15 bronze badges

Methods of converting an image to graph

Awarded Oct 3, 2014 at 12:53

B Faley

14110 bronze badges

Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph

Awarded Apr 2, 2014 at 7:49

Lior Kogan

5092 silver badges21 bronze badges

Bounds on the size of the smallest NFA for L_k-distinct

Awarded Mar 24, 2014 at 8:57

R B

9,3685 gold badges33 silver badges73 bronze badges

Partitioning graphs while minimizing inter-partition edges

Awarded Feb 26, 2014 at 15:59

zaloo

3831 silver badge13 bronze badges

Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion Question

Awarded Feb 24, 2014 at 22:26

Nizbel99

436 bronze badges

NP complete graph problems about structural properties

Awarded Nov 19, 2013 at 21:22

G. Bach

4312 silver badges17 bronze badges

Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$

Awarded Sep 1, 2013 at 8:57

Yixin Cao

2,5601 gold badge15 silver badges28 bronze badges

$FNP$ ,$ \#P$,$\oplus P$ classes

Awarded Aug 31, 2013 at 19:36

Fayez Abdlrazaq Deab

3591 silver badge11 bronze badges

Lower bound for testing closeness in $L_2$ norm?

Awarded Jul 23, 2013 at 14:16

Clement C.

4,38128 silver badges50 bronze badges

Application of methods from dynamical system to the study of k-SAT and similar problems

Awarded Jul 2, 2013 at 18:59

nonlinearism

738 bronze badges

Is there a book/survey-paper outlining language class hierarchies, closure properties, etc

Awarded Jun 7, 2013 at 19:10

Joey Eremondi

2,76414 silver badges29 bronze badges

Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs

Awarded May 30, 2013 at 9:11

Peter

4594 silver badges13 bronze badges

Implications of approximating the determinant

Awarded May 13, 2013 at 5:10

Lior Eldar

1,2246 silver badges14 bronze badges

Count the number of spanning trees fast

Awarded May 6, 2013 at 17:55

user197284

5952 silver badges11 bronze badges

Finding the perfomance ratio in a multicommodity-flow

Awarded Feb 27, 2013 at 7:50

hulik

1257 bronze badges

Exponential Speedup in External Memory

Awarded Feb 14, 2013 at 6:35

SamM

1,6572 gold badges14 silver badges21 bronze badges

Can Scheme's call/cc implement all known control flow structures?

Awarded Feb 8, 2013 at 21:29

csl

1339 bronze badges

Certified compiler and optimizations in Coq/Agda

Awarded Feb 7, 2013 at 19:03

mrsteve

4432 silver badges12 bronze badges

2 Next