Promoter

Promoter

First bounty you offer on your own question.

Awarded 235 times.

Deciding if all matrix multiplication entries have at least two witnesses

Awarded Jun 23 at 23:55

karmanaut

1,0155 silver badges15 bronze badges

Direct fpt reduction from Weighted 3SAT to Weighted 2SAT

Awarded May 21 at 3:57

Noel Arteche

4194 silver badges7 bronze badges

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

Awarded May 9 at 10:36

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 26 at 11:18

dohmatob

2171 silver badge10 bronze badges

(post deleted or otherwise unavailable)

Awarded Apr 19 at 20:25

Jake

6773 silver badges19 bronze badges

Semantics of logic/relational programming languages

Awarded Mar 26 at 18:57

Molossus Spondee

1116 bronze badges

Maximize the mutual information between 2 discrete random variables

Awarded Feb 8 at 3:47

wanderer

993 bronze badges

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

Hao S

2171 silver badge7 bronze badges

Algorithm for finding traffic equilibrium

Awarded Dec 8, 2021 at 11:07

Ace shinigami

675 bronze badges

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

Awarded Nov 26, 2021 at 2:12

Samuel Schlesinger

1,5526 silver badges20 bronze badges

Maximally Permissive Strategies for Safety Properties

Awarded Oct 4, 2021 at 7:50

kafka

3391 silver badge9 bronze badges

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

Awarded Sep 29, 2021 at 19:08

Inuyasha Yagami

1,3891 gold badge6 silver badges22 bronze badges

Applications of solvability in the λ-calculus

Awarded Sep 25, 2021 at 15:36

xavierm02

5213 silver badges11 bronze badges

Relationship between Random Graph Theory and TCS

Awarded Aug 27, 2021 at 2:18

MikeG

1136 bronze badges

Input length and calculation time to simulate a quantum measurement

Awarded Aug 26, 2021 at 11:33

Doriano Brogioli

213 bronze badges

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

Awarded Aug 5, 2021 at 21:26

Mathphile

1215 bronze badges

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

Awarded Jun 29, 2021 at 18:15

Henning

3892 silver badges12 bronze badges

Theorem on non-decreasing probability of success of an algorithm

Awarded Jun 23, 2021 at 14:45

fgrieu

1096 bronze badges

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

Awarded Jun 15, 2021 at 21:15

Ari

2851 silver badge6 bronze badges

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

Awarded May 23, 2021 at 3:11

Root

3873 silver badges11 bronze badges

How hard is this combinatorial optimisation problem?

Awarded May 19, 2021 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, 2020 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, 2020 at 10:18

Haden Hooyeon Lee

1578 bronze badges

How to calculate complexity in a high dimensional space?

Awarded Oct 22, 2020 at 16:32

user2827214

552 bronze badges

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

Awarded Oct 13, 2020 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, 2020 at 8:41

zdm

3251 silver badge10 bronze badges

Alternative exponential definition of Kolmogorov complexity

Awarded Sep 30, 2020 at 23:13

Jori

415 bronze badges

Estimating the cardinality of multisets given some sets of different sizes

Awarded Aug 29, 2020 at 4:42

user1246462

878 bronze badges

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

Awarded Aug 22, 2020 at 8:37

Bartosz Bednarczyk

1,1101 gold badge11 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, 2020 at 17:04

0x90

4632 silver badges13 bronze badges

(post deleted or otherwise unavailable)

Awarded Jun 3, 2020 at 11:28

2016310588

339 bronze badges

Diagonalization arguments for QMA type proof systems

Awarded May 23, 2020 at 8:07

AngryLion

1539 bronze badges

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

Awarded May 8, 2020 at 16:35

Bhishmaraj

3912 silver badges10 bronze badges

Hardness of approximating acyclic chromatic number

Awarded Feb 22, 2020 at 9:30

Cyriac Antony

1,6037 silver badges21 bronze badges

NP-hard problems with very fast exponential-time algorithms

Awarded Dec 29, 2019 at 16:40

vb le

4,82835 silver badges46 bronze badges

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

Awarded Dec 13, 2019 at 15:20

Timon Knigge

716 bronze badges

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

Awarded Dec 2, 2019 at 17:25

Naysh

4542 silver badges11 bronze badges

Can we map this problem to subset-sum?

Awarded Jul 16, 2019 at 11:25

AVIK DUTTA

453 bronze badges

Run Length eXtreme encoded length

Awarded Jul 15, 2019 at 16:55

boinkboink

17312 bronze badges

Planar Exact Cover by even-size sets

Awarded Jun 24, 2019 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, 2019 at 19:30

Vince Vatter

3191 silver badge9 bronze badges

A partition problem in which some numbers may be cut

Awarded Feb 2, 2019 at 22:40

Erel Segal-Halevi

1,8269 silver badges19 bronze badges

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

Awarded Jan 28, 2019 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, 2018 at 17:25

Lars Ericson

1073 bronze badges

Time complexity of exponentiating s-sparse matrices

Awarded Nov 6, 2018 at 18:20

Sanchayan Dutta

3071 silver badge7 bronze badges

Confusion about a formal definition of PRAM consistency

Awarded Aug 24, 2018 at 11:50

hengxin

2,3191 gold badge14 silver badges32 bronze badges

Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic

Awarded Jul 3, 2018 at 10:08

yters

2031 silver badge9 bronze badges

List of (unsolved) complexity problems arising from PL

Awarded Apr 11, 2018 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, 2018 at 0:28

Jika

1156 bronze badges

Realization of a bipolar orientation by a mixed graph

Awarded Mar 23, 2018 at 22:48

seteropere

4671 gold badge3 silver badges15 bronze badges

(post deleted or otherwise unavailable)

Awarded Jan 16, 2018 at 22:25

Don Fanucci

1537 bronze badges

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

Awarded Jan 12, 2018 at 17:22

Paul Knight

816 bronze badges

Visualizing the parse structure of a range concatenation grammar

Awarded Dec 29, 2017 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, 2017 at 20:17

mm8511

2031 silver badge8 bronze badges

Examples of quasilinear vs. essentially linear time translatable models

Awarded Nov 23, 2017 at 17:44

Dan Brumleve

5605 silver badges17 bronze badges

Program inversion algorithms for higher-order programs

Awarded Nov 13, 2017 at 11:44

Martin Berger

10.3k3 gold badges34 silver badges62 bronze badges

Bloom filter variant for constant-time subset/superset queries

Awarded Oct 31, 2017 at 15:54

Mike Battaglia

1995 bronze badges

Bipartite matching with degree domination

Awarded Oct 2, 2017 at 18:59

Wei Zhan

3282 silver badges13 bronze badges

Deciding the Most Significant Bit of Binary Multiplication

Awarded Sep 9, 2017 at 17:48

Heyheyhey

1841 silver badge11 bronze badges

Graph rewriting with one-to-many pattern matching?

Awarded Jun 22, 2017 at 2:42

James Koppel

4552 silver badges9 bronze badges

2 3 4 Next

Stack Exchange Network

current community

your communities

more stack exchange communities