Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top
Theoretical Computer Science

Top Questions

Ask Question
Active Hot Week Month
0 votes
0 answers
12 views

Nonlinear GAP similar to Min-GAP but with minimum quantities and without capacity

Jika's user avatar
Jika
  • 115
3 votes
0 answers
57 views

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

rus9384's user avatar
rus9384
  • 275
0 votes
1 answer
206 views

Any analogues to Turing-Church thesis out there? [closed]

Emil Jeřábek's user avatar
Emil Jeřábek
  • 16.9k
-2 votes
1 answer
86 views

Proof that DFS order is P-complete

Robin Petr's user avatar
Robin Petr
  • 1
5 votes
0 answers
121 views

Variation of (derandomized) Valiant-Vazirani

Noel Arteche's user avatar
Noel Arteche
  • 871
1 vote
0 answers
69 views

Is it possible to recover the set of derivation trees of a fact from its semiring provenance in Datalog?

Justin Lubin's user avatar
Justin Lubin
  • 11
0 votes
0 answers
49 views

Hardness for find the clause for statisfiable 3-SAT problems

ironmanaudi's user avatar
ironmanaudi
  • 101
8 votes
1 answer
403 views

What can we do with a generic oracle (as opposed to a random one)?

Emil Jeřábek's user avatar
Emil Jeřábek
  • 16.9k
1 vote
0 answers
65 views

How often can a clause cause a conflict?

Russell Easterly's user avatar
Russell Easterly
  • 559
6 votes
2 answers
435 views

Error in Robson's proof about separating strings?

Hermann Gruber's user avatar
Hermann Gruber
  • 5,840
5 votes
1 answer
149 views

Can CDCL Algorithm Derived Conflict Clauses Always Be Obtained Through Resolution from an Unsatisfiable CNF Formula?

holf's user avatar
holf
  • 2,164
16 votes
2 answers
1k views

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

Michael Lampis's user avatar
Michael Lampis
  • 3,416
1 vote
0 answers
39 views

Find the SVM kernel in detecting if a substring in a given string

Tran Khanh's user avatar
Tran Khanh
  • 131
-1 votes
0 answers
32 views

corresponding resoving and arbitary resolving

Jxb's user avatar
Jxb
  • 315
-1 votes
0 answers
82 views

Proof for Upper Bound on the Size of the Sum of Rational Numbers

Arcade_TryHard's user avatar
Arcade_TryHard
  • 1
2 votes
0 answers
54 views

Is the Category of $(* \to)^n *$-kinded types freely generated from the discrete graph with $n$ nodes?

Johan Thiborg-Ericson's user avatar
Johan Thiborg-Ericson
  • 121
0 votes
1 answer
103 views

Confusion about lower bounds and upper bounds in learning theory

Aryeh's user avatar
Aryeh
  • 10.3k
4 votes
0 answers
122 views

Convex optimization: is it possible to find solutions that are exactly feasible and approximately optimal in polynomial time?

Erel Segal-Halevi's user avatar
Erel Segal-Halevi
  • 2,078
2 votes
0 answers
72 views

Enforcing general position in $2d$ linear programming

user3508551's user avatar
user3508551
  • 1,078
1 vote
1 answer
102 views

Known Variant of Set Cover?

Jiwon Chang's user avatar
Jiwon Chang
  • 21
2 votes
2 answers
434 views

Technical limitations of Turing machines due to the input and output encoding of values

Gro-Tsen's user avatar
Gro-Tsen
  • 619
1 vote
1 answer
126 views

Are there any algorithms that the brain is better at solving than a regular computer? How would these be found/verified?

Command Master's user avatar
Command Master
  • 464
2 votes
0 answers
59 views

Many-one equivalence of sets that differ finitely

ijon's user avatar
ijon
  • 33
0 votes
0 answers
41 views

Approximation ratio of randomized rounding for integral multi-commodity flow

Recursion's user avatar
Recursion
  • 1
4 votes
2 answers
522 views

Do we currently know a polynomial-size Frege proof for Tseitin formulas?

Emil Jeřábek's user avatar
Emil Jeřábek
  • 16.9k
-2 votes
1 answer
61 views

What is really the difference between membership queries and "querying in i.i.d?

Aryeh's user avatar
Aryeh
  • 10.3k
17 votes
0 answers
1k views

Are theoretical computer science conferences losing touch with reality?

kodlu's user avatar
kodlu
  • 2,070
4 votes
1 answer
142 views

Connection between strong normalization of the simply typed λ-calculus, and cut elimination for propositional logic

gadmm's user avatar
gadmm
  • 307
1 vote
1 answer
101 views

Balanced set coloring

TheHolyJoker's user avatar
TheHolyJoker
  • 136
3 votes
1 answer
169 views

What’s the complexity of this decision problem with bit shifting?

D.W.'s user avatar
D.W.
  • 11.7k
-2 votes
0 answers
46 views

d-regular graphs and edge expanders

math-nerd-in-cs's user avatar
math-nerd-in-cs
  • 1
0 votes
0 answers
92 views

Relationships between problem symmetry and its complexity

Ayoubayjx's user avatar
Ayoubayjx
  • 122
3 votes
1 answer
345 views

Intuition on Lupanov's Upper Bound on Circuit Size

Vladimir Lysikov's user avatar
Vladimir Lysikov
  • 632
2 votes
2 answers
81 views

Learning with zero inductive bias

Aryeh's user avatar
Aryeh
  • 10.3k
-2 votes
0 answers
43 views

Greedy rounding technique

LyLa's user avatar
LyLa
  • 1
-1 votes
0 answers
64 views

What are you favorite techniques at finding lower bounds?

rivana's user avatar
rivana
  • 53
3 votes
2 answers
256 views

Where should I apply for MS in CS if I want to get admitted for Phd in TCS

Vinicius dos Santos's user avatar
Vinicius dos Santos
  • 1,868
4 votes
1 answer
103 views

Lower bound for constant degree monotone arithmetic circuits

Robert Andrews's user avatar
Robert Andrews
  • 743
-1 votes
0 answers
26 views

Finding an algorithm EF[1,1] and PO division for more than two agents

S. M.'s user avatar
S. M.
  • 99
0 votes
1 answer
59 views

Learning positive half-lines (in $\mathbb{N}$)

Aryeh's user avatar
Aryeh
  • 10.3k
-1 votes
0 answers
50 views

Average case complexity of decision version of NP-hard problem

Subhra Mazumdar's user avatar
Subhra Mazumdar
  • 99
1 vote
0 answers
64 views

Crafting ${NP}^{\#P}$-complete problems

Habri's user avatar
Habri
  • 11
6 votes
0 answers
64 views

Updating (minimal) DFA incrementally

gsv's user avatar
gsv
  • 421
1 vote
1 answer
78 views

Learning arithmetic series

Aryeh's user avatar
Aryeh
  • 10.3k
10 votes
0 answers
204 views

Is there a text that discusses both the “lambda cube” of pure type theories and Martin-Löf's intuitionistic type theories, and compares them?

Gro-Tsen's user avatar
Gro-Tsen
  • 619
1 vote
0 answers
39 views

what are some Lower bound for finding large fourier coefficients of boolean function (above a threshold)?

rivana's user avatar
rivana
  • 53

Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.