Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
25
votes
5 answers

Mathematical implications of complexity theory conjectures outside TCS

Do you know interesting consequences of (standard) conjectures in complexity theory in other fields of mathematics (i.e. outside of theoretical computer science)? I would prefer answers where: the complexity theory conjecture is as general and…
Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
25
votes
1 answer

Is cubic complexity still the state of the art for LP?

According to D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, 1994, a linear program with $n$ variables, $n$ constraints and precision $L$ is solvable in $O(n^3L)$ time. Has that been improved upon?
Aryeh
  • 10,494
  • 1
  • 27
  • 51
25
votes
2 answers

Why do Agda and Coq disagree on strict positivity?

I've stumbled across a confusing disagreement between Agda and Coq that is not obviously related to the most well known distinctions between their type theories (e.g., (im)predicativity, induction-recursion, etc.). In particular, the following…
Colin Gordon
  • 471
  • 4
  • 9
25
votes
2 answers

Is finding Logspace reductions harder than P reductions?

Motivated by Shor's answer related to different notions of NP-completeness, I am looking for a problem that is NP-complete under P reductions but not known to be NP-complete under Logspace reductions (preferably for a long time). Also, Is finding…
Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
25
votes
2 answers

Approximating the sign rank of a matrix

The sign rank of a matrix A with +1,-1 entries is the least rank (over the reals) of a matrix B which has the same sign pattern as A (i.e., $A_{ij}B_{ij}>0$ for all $i,j$). This notion is important in communication complexity and learning theory. My…
Moritz
  • 1,714
  • 15
  • 21
25
votes
4 answers

Best known deterministic time complexity lower bound for a natural problem in NP

This answer to Major unsolved problems in theoretical computer science? question states that it is open if a particular problem in NP requires $\Omega(n^2)$ time. Looking at the comments under answer made me wonder: Aside from padding and similar…
Anonymous
  • 4,041
  • 19
  • 43
25
votes
3 answers

Constructivity in Natural Proof and Geometric Complexity

Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$. Constructivity in Natural Proof is a condition that all combinatorial proofs…
auyun
  • 251
  • 2
  • 2
25
votes
1 answer

Regularity Lemma for Sparse Graphs

Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets such that most pairs of sets form bipartite…
Dana Moshkovitz
  • 10,979
  • 1
  • 50
  • 77
25
votes
2 answers

Sum-of-squares proof system

Recently I have seen several articles on arxiv that refer to a proof system called sum-of-squares. Can someone explain what is a sum-of-squares proof and why such proofs are important/interesting? How are they related to other algebraic proof…
Anonymous
  • 4,041
  • 19
  • 43
25
votes
4 answers

Proofs, Barriers and P vs NP

It is well known that any proof resolving the P vs NP question must overcome relativization, natural proofs and algebrization barriers. The following diagram partitions the "proof space" into different regions. For example, $RN$ corresponds to the…
Shiva Kintali
  • 10,578
  • 41
  • 74
25
votes
3 answers

Rounding to minimise the sum of errors in pairwise distances

What is known about the complexity of the following problem: Given: rational numbers $x_1 < x_2 < \dotso < x_n$. Output: integers $y_1 \le y_2 \le \dotso \le y_n$. Objective: minimise $$\sum_{1 \le i < j \le n} e(i,j),$$ where $$e(i,j) = |…
Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
25
votes
1 answer

What's the expressive power of Simply Typed Lambda calculus?

The standard approach to simply typed lambda calculus considers computations over Church numerals. If input and outputs are Church numerals always typed as $Int$, where $Int = (\tau \rightarrow \tau) \rightarrow \tau \rightarrow \tau $, a result of…
Mycol
  • 411
  • 3
  • 4
25
votes
1 answer

Approximate degree of $\textrm{AC}^0$

EDIT (v2): Added a section at the end on what I know about the problem. EDIT (v3): Added discussion on threshold degree at the end. Question This question is mainly a reference request. I don't know much about the problem. I want to know if there…
Robin Kothari
  • 13,617
  • 2
  • 60
  • 116
25
votes
1 answer

What is $\mathsf{NP}$ restricted to linear size witnesses?

This is related to the question Is the Witness Size of Membership for Every NP Language Already Known? Some natural $\mathsf{NP}$(-complete) problems have linear length witnesses: a satisfying assignment for $SAT$, a sequence of vertices for…
argentpepper
  • 2,281
  • 15
  • 27
25
votes
3 answers

Regular languages from category-theoretical point of view

I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a strict monoidal structure on this category that…
Aleksei Averchenko
  • 353
  • 3
  • 6
1 2 3
…
99 100