Scholar - Badge - Theoretical Computer Science Stack Exchange

Scholar

Ask a question and accept an answer.

Awarded 2610 times.

K-Clustering of a Graph maximizing intra-cluster weights?

Awarded 10 hours ago

Steven

2631 silver badge9 bronze badges

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

Awarded Nov 21 at 4:36

Junqiang Peng

1637 bronze badges

Learning with zero inductive bias

Awarded Nov 19 at 17:16

rivana

534 bronze badges

Learning arithmetic series

Awarded Nov 15 at 19:56

meeeeee

214 bronze badges

High-dimensional expanders through the lens of algebraic topology

Awarded Nov 15 at 8:47

p-adict

433 bronze badges

Intuition on Lupanov's Upper Bound on Circuit Size

Awarded Nov 14 at 20:21

sdsdsd

1332 bronze badges

Why is it impossible to prove software to be correct?

Awarded Nov 13 at 10:55

student

32 bronze badges

Unable to understand the Sample complexity of PAC learning

Awarded Nov 10 at 4:08

Sathishkumar Thirumalai

11 bronze badge

Many-one degrees of some particular sets

Awarded Oct 28 at 22:41

ijon

332 bronze badges

In the age of powerful AI, can all software be written using only tests?

Awarded Oct 25 at 18:41

Maciej Bledkowski

1615 bronze badges

Finding deepest intersection

Awarded Oct 23 at 13:37

femeve3881

31 bronze badge

Complexity of analytic functions and integrals

Awarded Oct 13 at 15:35

roignoirewg

133 bronze badges

Fast algorithms for time bounded Kolmogorov complexity

Awarded Oct 8 at 18:32

agemO

1874 bronze badges

Is is true that every monad transformer is equivalent to its underlying/base monad?

Awarded Oct 1 at 10:42

Russoul

2094 bronze badges

Assignment problem for forming pairs of real numbers

Awarded Sep 25 at 12:22

calmcc

1614 bronze badges

Independent set queries with preprocessing

Awarded Sep 23 at 3:11

Command Master

4641 silver badge9 bronze badges

Is there a well-defined notion of an “R/poly” complexity class?

Awarded Sep 10 at 20:10

Colonizor48

3311 silver badge5 bronze badges

What is the type of the lambda term $\lambda a.a(\lambda yt.t)(ya)$?

Awarded Sep 9 at 9:57

Domiziano Scarcelli

1112 bronze badges

Power of non-implicationally-complete Frege systems and Boolean equational calculus

Awarded Sep 8 at 17:31

Soha

1456 bronze badges

Complexity of the inevitability problem over monoids

Awarded Sep 6 at 17:58

Rémi

1437 bronze badges

Structural Complexity Theory References

Awarded Aug 24 at 5:19

LiminalSpace

1137 bronze badges

Name and complexity of a stone placement puzzle

Awarded Aug 17 at 20:26

TRP

313 bronze badges

Can you regain the Church-Rosser property in languages with continuations?

Awarded Aug 13 at 4:55

idka

813 bronze badges

Can the initial algebra of a 2-variable polynomial functor be computed on the diagonal?

Awarded Aug 7 at 16:16

sparusaurata

1997 bronze badges

Shortest Common Supersequence of Permutations

Awarded Aug 3 at 7:25

igel

1858 bronze badges

What kind of resolution is CDCL corresponding to?

Awarded Aug 1 at 14:36

Jxb

3151 silver badge9 bronze badges

What is a very simple pseudodeterministic algorithm (for educational purposes)?

Awarded Jul 30 at 2:42

user69687

1334 bronze badges

clique problem in graphs with bounded degree

Awarded Jul 19 at 13:50

Michael Poss

233 bronze badges

Algorithm for comparing list elements backwards

Awarded Jul 18 at 19:35

loop_orange

132 bronze badges

Is $a^m b^n$ where $m - n \sqrt{2} \ge 0$ context-free?

Awarded Jul 18 at 5:04

bb94

1234 bronze badges

Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?

Awarded Jul 17 at 20:17

edit

333 bronze badges

Maximizing merges with restrictions

Awarded Jul 17 at 18:35

Adam Jamil

134 bronze badges

What is "structural model checking"?

Awarded Jul 16 at 9:09

Senmorta

133 bronze badges

Most Matrices are Rigid

Awarded Jul 12 at 20:36

atul ganju

1435 bronze badges

Enumerating part of an arrangement

Awarded Jul 11 at 21:27

Jarus

387 bronze badges

What is the solution of this equation on regular languages?

Awarded Jul 9 at 19:49

Pietro Braione

1334 bronze badges

Is Linear Evaluation Parametric?

Awarded Jul 8 at 22:36

vigenary

933 bronze badges

Probabilistic Logic Programming vs Stochastic Logic Programming

Awarded Jul 7 at 9:20

Pav

32 bronze badges

Lower bound for the Schwartz–Zippel lemma in Polynomial Hashing

Awarded Jun 30 at 16:50

catalyst

234 bronze badges

Is it necessary to apply alpha conversion in this term to perform beta reduction in lambda calculus?

Awarded Jun 29 at 6:08

AdrianGarciaB

31 bronze badge

Maximum cardinality matching on DAGs

Awarded Jun 27 at 12:55

Marco Pegoraro

333 bronze badges

Complexity of "opposite" version of a variant of #Positive-2-SAT

Awarded Jun 22 at 12:58

Anuj

133 bronze badges

Probabilistic Turing machine of possibly correlated choices

Awarded Jun 9 at 15:10

namasikanam

1135 bronze badges

Fine-grained average-case derandomization

Awarded Jun 5 at 9:33

Nicholas Brandt

2231 silver badge4 bronze badges

What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?

Awarded May 28 at 18:34

Marion

1835 bronze badges

Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

Awarded May 27 at 9:20

Thiago

1194 bronze badges

Complexity of polygon intersection test

Awarded May 23 at 17:34

Lieven

1234 bronze badges

Type of the Recursor in Lean

Awarded May 19 at 21:32

Alex Byard

1135 bronze badges

(post deleted or otherwise unavailable)

Awarded May 13 at 22:57

Jack

12 bronze badges

Can I define nested mutually dependent types in Coq?

Awarded May 13 at 15:52

Henri_S

132 bronze badges

NP-complete problems on posets?

Awarded May 9 at 22:01

Ctenochaetus

333 bronze badges

Does being able to efficiently factor semiprimes allow to efficiently factor any integer?

Awarded May 5 at 8:16

glS

1427 bronze badges

6-regular graph without small 3-regular subgraph

Awarded May 4 at 6:57

Balchandar Reddy

635 bronze badges

Why isn't the proof obtained using Buss's proof of the derivational completeness of LK anchored?

Awarded Apr 20 at 17:36

Johnny

2015 bronze badges

Is $GapCVP_{\gamma} \in coAM$ for all $\gamma$?

Awarded Apr 20 at 13:16

kerf

133 bronze badges

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

bubakazouba

1134 bronze badges

Where can I find more information about "dependent elimination"?

Awarded Apr 14 at 15:02

Valmir Junior

234 bronze badges

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

emmy

1233 bronze badges

(post deleted or otherwise unavailable)

Awarded Apr 10 at 17:34

David

1012 bronze badges

How far is the distance between Mahlo Universe and Mahlo Cardinal?

Awarded Apr 9 at 12:33

Ember Edison

1516 bronze badges

2 3 4 5

…

44 Next