31
votes
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for ...
- 411
30
votes
Accepted
Is Descriptive Complexity dead?
I also have the impression that Descriptive Complexity is a less active area of research nowadays. Nevertheless, there are some topics in which people are still active:
Rank logics:
Rank Logic is ...
- 1,422
28
votes
Theoretical explanations for practical success of SAT solvers?
I am assuming that you are referring to CDCL SAT solvers on benchmark data sets
like those used in the SAT Competition.
These programs are based on many heuristics and lots of optimization.
There were ...
- 21.8k
24
votes
Theoretical explanations for practical success of SAT solvers?
I am typing this quite quickly due to severe time constraints (and didn't even get to responding earlier for the same reason), but I thought I would try to at least chip in with my two cents.
I ...
- 554
19
votes
Theoretical explanations for practical success of SAT solvers?
I'm not an expert in this area, but I think the random SAT / phase transition stuff is more or less completely unrelated to the industrial/practical applications stuff.
E.g., the very good solvers ...
- 1,811
19
votes
What is the "question" that programming language theory is trying to answer?
The overall purpose of PLT is to make industrial software
engineering (in a general sense) cheaper (also in a general sense), through optimising the most
important tool (programming languages) and ...
- 11.6k
18
votes
Theoretical explanations for practical success of SAT solvers?
Let me add my two cents of understanding to this, even though I've never actually worked in the area.
You're asking one of two questions, "what are all the known approaches to proving theoretical ...
- 843
17
votes
Theoretical explanations for practical success of SAT solvers?
There is a paper "Relating Proof Complexity Measures and Practical Hardness of SAT" by Matti Järvisalo, Arie Matsliah, Jakob Nordström, and Stanislav Živný in CP '12 that attempts to link the hardness ...
- 4,765
17
votes
Possible to do Complexity theory with only counting and Pigeonhole
If you are looking for non-pigeon-hole type arguments, then there is good news: they exist! The pigeon-hole principle is a certain template for proof by contradiction. There are concepts in TCS which ...
- 2,194
16
votes
Accepted
What CS theories are absolutely paramount for someone new to TCS to understand?
(Disclaimer: this answer has a focus on programming languages theory, which is only one of the many disciplines under the TCS umbrella.
Apologies for the length.)
A small digression
You are asking ...
- 688
15
votes
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
Well, one thing is I think that all the constructions we know of - and even the families of potential constructions that people have proposed (e.g., Cohn-Umans approaches, generalizations of ...
- 38.5k
15
votes
Is Descriptive Complexity dead?
Definitely still active in the area of Weisfeiler-Leman-style algorithms for isomorphism problems such as Graph Isomorphism. The connection with logic was first (I believe) made in Immerman-Lander ...
- 38.5k
12
votes
Implications of unprovability of $P\neq NP$
As proved in the paper "On The Independence of P Versus NP" by S. Ben-David and S. Halevi:
If $P \neq NP$ can be shown to be independent
of Peano Arithmetic, then NP has extremely-close-to-...
- 1,616
9
votes
Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?
A formalism is useful or not, based on what people want to use the formalism to model and understand.
The Turing machine is a formalism that is useful for understanding programs. Programs are worth ...
- 2,356
9
votes
Why exactly are complexity theorists interested in closed timelike curves?
Sorry for the very "big picture" answer from a non-quantum-theorist, but this contrast might help: you could describe algorithms as the study of how to solve computational problems, whereas complexity ...
- 7,788
9
votes
Accepted
Why exactly are complexity theorists interested in closed timelike curves?
I think the big question here is "What does the complexity/power of algorithms look like in our universe?" If we ignore relativity and QM, then plain vanilla Turing machines are a decent model. But ...
- 38.5k
8
votes
Accepted
How powerful is $ACC^0$ circuit class in average case?
There seem to be typos in what you wrote; I take it you're asking: is there a function $f \in NEXP$ such that for all polynomials $p$ and infinitely many $n$, no ACC0 circuit of $p(n)$ size can ...
- 27.7k
8
votes
possible bridge between group growth theory and complexity theory?
Maybe this is along the lines you are looking for: I wrote a blog post here explaining how you can use Gromov's theorem on groups of polynomial growth to show that non-uniform read once automata are ...
- 431
8
votes
Accepted
Is Biological Computation a theme covered by the Theoretical Computer Science?
Yes there is some overlap, for instance the conference Unconventional Computation and Natural Computation (UCNC) covers theoretical computer science topics related to biological computation.
From the ...
- 4,495
8
votes
Accepted
Qubit gates in google supremacy
Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They ...
- 25k
7
votes
Accepted
Implications of faster randomized $CIRCUIT SAT$ algorithm
The gist of the proof of the proposition you're talking about is to simply cite that $EXP\subset P/poly$ implies $EXP=\Sigma_2^p$ (there is a short proof of this in the Arora and Barak book in the ...
- 573
7
votes
Accepted
Consequences of faster parameterized integer programming
An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally ...
- 5,285
7
votes
How does one "understand" complexity theory?
It's a nice question, but before partially answering it I want to question part of the premise.
My main thesis here is that all mathematical fields are actually just loosely coherent collections of &...
- 38.5k
6
votes
Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)
Some of the work of Olivier Finkel seems related to the question---though not necessarily explicitly about the Axiom of Choice itself---and in line with Timothy Chow's answer. For instance, quoting ...
- 3,374
6
votes
Accepted
Fixed parameter tractable Integer Programming and $FPP$
You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^*$, whereas parameterized decision problems are ...
- 396
6
votes
Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?
It would be a very interesting result if one were able to present a language in BPP that is hard for RP (equivalently, for co-RP) under poly-time Turing reducibility (aka Cook reducibility). I'm ...
- 2,356
6
votes
Concepts that go into converting an Algorithm to a hardware implementation of it
I was in the same position a couple of years ago, when I took the plunge from software and PL theory to hardware verification. I too looked here for help (see this question)
Unfortunately, there is ...
- 11.6k
5
votes
Benefits for syntactic and semantic classes
Here are a couple of advantages.
Syntactic classes give you time hierarchies. Zak's proof of the nondeterministic time hierarchy works for any syntactic class. For semantic classes (like UPTIME($n^3$...
- 8,791
5
votes
On integer programming
It's NP-hard. Given an integer programming problem $P$, add an irrelevant variable $z$ with no constraints; call the resulting problem $P'$. Now if $P$ has no solutions, then $P'$ has no solutions; ...
- 12.4k
Only top scored, non community-wiki answers of a minimum length are eligible