Promoter

Promoter

First bounty you offer on your own question.

Awarded 220 times.

NP-hardness for one-dimensional facility location problem with entrance fee for each customer [closed]

Awarded Dec 29 '20 at 8:55

asdfqwer

895 bronze badges

Time complexity for a variant of edit distance

Awarded Dec 12 '20 at 15:46

Anush

1315 bronze badges

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

Awarded Nov 12 '20 at 10:18

Haden Hooyeon Lee

1578 bronze badges

How to calculate complexity in a high dimensional space?

Awarded Oct 22 '20 at 16:32

user2827214

552 bronze badges

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

Awarded Oct 13 '20 at 0:06

padawan

939 bronze badges

Is there a competitive algorithm for this online scheduling problem to minimize the truncated gaps?

Awarded Oct 12 '20 at 8:41

zdm

2751 silver badge9 bronze badges

Alternative exponential definition of Kolmogorov complexity

Awarded Sep 30 '20 at 23:13

Jori

415 bronze badges

Estimating the cardinality of multisets given some sets of different sizes

Awarded Aug 29 '20 at 4:42

user1246462

837 bronze badges

Order-invariant conjunctive queries are FO-definable without the order

Awarded Aug 22 '20 at 8:37

Bartosz Bednarczyk

9456 silver badges15 bronze badges

Complexity of finding the most likely edge

Awarded Aug 11 '20 at 15:04

donald

1757 bronze badges

Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?

Awarded Jul 3 '20 at 17:04

0x90

4532 silver badges13 bronze badges

(post deleted or otherwise unavailable)

Awarded Jun 3 '20 at 11:28

2016310588

339 bronze badges

Diagonalization arguments for QMA type proof systems

Awarded May 23 '20 at 8:07

AngryLion

796 bronze badges

Are there any public synchronous discussion forums (slack, discord, etc.) for TCS

Awarded May 8 '20 at 16:35

Bhishmaraj

3912 silver badges10 bronze badges

Hardness of approximating acyclic chromatic number

Awarded Feb 22 '20 at 9:30

Cyriac Antony

1,2515 silver badges20 bronze badges

NP-hard problems with very fast exponential-time algorithms

Awarded Dec 29 '19 at 16:40

vb le

4,77833 silver badges46 bronze badges

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

Awarded Dec 13 '19 at 15:20

Timon Knigge

716 bronze badges

What are some examples of algorithmic applications of noncommutative rational identity testing?

Awarded Dec 2 '19 at 17:25

Naysh

3521 silver badge8 bronze badges

Can we map this problem to subset-sum?

Awarded Jul 16 '19 at 11:25

AVIK DUTTA

453 bronze badges

Run Length eXtreme encoded length

Awarded Jul 15 '19 at 16:55

boinkboink

17312 bronze badges

Planar Exact Cover by even-size sets

Awarded Jun 24 '19 at 12:35

Yota Otachi

1,72115 silver badges24 bronze badges

Reference request: exponential growth rates of subsequence-closed languages are integers

Awarded Mar 9 '19 at 19:30

Vince Vatter

3211 silver badge9 bronze badges

A partition problem in which some numbers may be cut

Awarded Feb 2 '19 at 22:40

Erel Segal-Halevi

1,6188 silver badges19 bronze badges

Is case analysis on normal forms of lambda terms sufficient to prove parametricity results?

Awarded Jan 28 '19 at 18:30

Łukasz Lew

1,1373 silver badges12 bronze badges

A least sized partition of a set under a distance metric

Awarded Nov 12 '18 at 17:25

Lars Ericson

1073 bronze badges

Time complexity of exponentiating s-sparse matrices

Awarded Nov 6 '18 at 18:20

Sanchayan Dutta

3071 silver badge7 bronze badges

Confusion about a formal definition of PRAM consistency

Awarded Aug 24 '18 at 11:50

hengxin

2,2991 gold badge13 silver badges29 bronze badges

Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic

Awarded Jul 3 '18 at 10:08

yters

2031 silver badge9 bronze badges

List of (unsolved) complexity problems arising from PL

Awarded Apr 11 '18 at 0:19

xrq

1,1153 silver badges14 bronze badges

Can we find a generic tight example for the greedy algorithm of the unweighted generalized assignment problem?

Awarded Apr 8 '18 at 0:28

Jika

1156 bronze badges

Realization of a bipolar orientation by a mixed graph

Awarded Mar 23 '18 at 22:48

seteropere

4671 gold badge3 silver badges14 bronze badges

(post deleted or otherwise unavailable)

Awarded Jan 16 '18 at 22:25

Don Fanucci

1537 bronze badges

Is Non-linear Constrained Optimal Exact Cover NP-Hard?

Awarded Jan 12 '18 at 17:22

Paul Knight

816 bronze badges

Visualizing the parse structure of a range concatenation grammar

Awarded Dec 29 '17 at 22:50

kakashi10192020

1036 bronze badges

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

Awarded Dec 4 '17 at 20:17

mm8511

2031 silver badge8 bronze badges

Examples of quasilinear vs. essentially linear time translatable models

Awarded Nov 23 '17 at 17:44

Dan Brumleve

5605 silver badges17 bronze badges

Program inversion algorithms for higher-order programs

Awarded Nov 13 '17 at 11:44

Martin Berger

10k3 gold badges33 silver badges62 bronze badges

Bloom filter variant for constant-time subset/superset queries

Awarded Oct 31 '17 at 15:54

Mike Battaglia

1995 bronze badges

Bipartite matching with degree domination

Awarded Oct 2 '17 at 18:59

Willard Zhan

3182 silver badges13 bronze badges

Deciding the Most Significant Bit of Binary Multiplication

Awarded Sep 9 '17 at 17:48

Heyheyhey

1741 silver badge11 bronze badges

Graph rewriting with one-to-many pattern matching?

Awarded Jun 22 '17 at 2:42

James Koppel

4452 silver badges9 bronze badges

Approximating the Radius of a (Dense) Graph

Awarded Jun 17 '17 at 14:52

Mohemnist

2281 silver badge7 bronze badges

Pumping Lemma over 2 way Automaton

Awarded Jun 9 '17 at 6:20

TheoryQuest1

7493 silver badges12 bronze badges

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

Awarded Apr 29 '17 at 20:27

Michael Wehar

4,8001 gold badge18 silver badges47 bronze badges

When can be used the “uncompute garbage” trick in quantum computing?

Awarded Apr 26 '17 at 5:29

permanganate

2631 silver badge10 bronze badges

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

Awarded Mar 1 '17 at 2:22

Omar Shehab

1,0338 silver badges20 bronze badges

A subset grouping problem

Awarded Feb 10 '17 at 23:21

user357269

836 bronze badges

(post deleted or otherwise unavailable)

Awarded Feb 7 '17 at 22:01

milo

1011 bronze badge

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

Awarded Nov 5 '16 at 14:59

cody

12.6k1 gold badge38 silver badges78 bronze badges

Constructing subfields of a finite field

Awarded Oct 23 '16 at 22:12

xyz

2431 silver badge7 bronze badges

(post deleted or otherwise unavailable)

Awarded Oct 23 '16 at 14:24

Parham

2352 silver badges9 bronze badges

Context-Sensitive Grammar characteristic properties

Awarded Oct 22 '16 at 12:58

Andrey Lebedev

6054 silver badges16 bronze badges

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

Awarded Jul 23 '16 at 13:15

TomR

4093 silver badges10 bronze badges

algorithms for a large submatrix / general factor / quasi-biclique problem?

Awarded Jul 8 '16 at 21:06

DavidDLewis

1456 bronze badges

reference request: deciding validity of higher-order quantified boolean formulas is not Kalmar-elementary

Awarded Jun 13 '16 at 16:12

Noam Zeilberger

4,15120 silver badges31 bronze badges

Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits?

Awarded Jun 6 '16 at 12:14

Alexey Milovanov

1,5196 silver badges19 bronze badges

Number of ordinal trees with n nodes, of depth d, with l leaves

Awarded May 31 '16 at 14:39

Jeremy

2,3411 gold badge17 silver badges28 bronze badges

Vertex Disjoint Path Covers of Hypercube-Like Graphs

Awarded May 12 '16 at 18:47

user340082710

914 bronze badges

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

Awarded May 11 '16 at 4:22

user25957

536 bronze badges

How to generate Extended Finite State Machines Randomly with some properties?

Awarded Apr 29 '16 at 7:32

Elaqqad

874 bronze badges

2 3 4 Next

Stack Exchange Network

current community

your communities

more stack exchange communities