Promoter

Promoter

First bounty you offer on your own question.

Awarded 228 times.

What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?

Awarded Dec 22 '21 at 5:57

Hao S

1791 silver badge7 bronze badges

Algorithm for finding traffic equilibrium

Awarded Dec 8 '21 at 11:07

Ace shinigami

675 bronze badges

Do random functions have synchronous, alternating circuits with non-injective first layers?

Awarded Nov 26 '21 at 2:12

Samuel Schlesinger

1,5526 silver badges20 bronze badges

Maximally Permissive Strategies for Safety Properties

Awarded Oct 4 '21 at 7:50

kafka

3271 silver badge9 bronze badges

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

Awarded Sep 29 '21 at 19:08

Inuyasha Yagami

1,3691 gold badge5 silver badges22 bronze badges

Applications of solvability in the λ-calculus

Awarded Sep 25 '21 at 15:36

xavierm02

4913 silver badges11 bronze badges

Relationship between Random Graph Theory and TCS

Awarded Aug 27 '21 at 2:18

MikeG

1136 bronze badges

Input length and calculation time to simulate a quantum measurement

Awarded Aug 26 '21 at 11:33

Doriano Brogioli

113 bronze badges

Problem in the paper "Stable Minimum Space Partitioning in Linear Time"

Awarded Aug 5 '21 at 21:26

Mathphile

1215 bronze badges

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

Awarded Jun 29 '21 at 18:15

Henning

3892 silver badges12 bronze badges

Theorem on non-decreasing probability of success of an algorithm

Awarded Jun 23 '21 at 14:45

fgrieu

1096 bronze badges

How is a "low-degree polynomial" precisely defined in Algebrization?

Awarded Jun 15 '21 at 21:15

Ari

2851 silver badge6 bronze badges

Computational complexity of minimum distance of rate $\frac{1}{2}$ codes

Awarded May 23 '21 at 3:11

Root

3053 silver badges11 bronze badges

How hard is this combinatorial optimisation problem?

Awarded May 19 '21 at 9:26

Rise of Kingdom

676 bronze badges

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

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

877 bronze badges

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

Awarded Aug 22 '20 at 8:37

Bartosz Bednarczyk

1,0701 gold badge10 silver badges17 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

4632 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

1219 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,4457 silver badges20 bronze badges

NP-hard problems with very fast exponential-time algorithms

Awarded Dec 29 '19 at 16:40

vb le

4,82835 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

4422 silver badges11 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,8029 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,1474 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,3091 gold badge14 silver badges31 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,1255 silver badges15 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

10.2k3 gold badges34 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

Wei Zhan

3182 silver badges13 bronze badges

Deciding the Most Significant Bit of Binary Multiplication

Awarded Sep 9 '17 at 17:48

Heyheyhey

1841 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

2301 silver badge8 bronze badges

Pumping Lemma over 2 way Automaton

Awarded Jun 9 '17 at 6:20

TheoryQuest1

7793 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,9101 gold badge18 silver badges49 bronze badges

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

Awarded Apr 26 '17 at 5:29

permanganate

2831 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

9599 silver badges21 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

2 3 4 Next

Stack Exchange Network

current community

your communities

more stack exchange communities