Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
16
votes
2 answers

Collatz Conjecture & Grammars / Automata

I was wondering if there is a good bibliography of attempts to investigate the Collatz conjecture as a formal grammar? (or any other attempts in the CS community to deal with this class of generative phenomena & their "halting" properties).
Deniz
  • 263
  • 1
  • 6
16
votes
1 answer

More efficient non-uniform derandomization ?

Adleman, FOCS'78 showed that any randomized circuit for inputs of length $n$ can be non-uniformly derandomized. However, the construction effectively duplicates the original circuit $O(n)$ times, so the derandomized circuit is larger than the…
Piotr
  • 971
  • 7
  • 15
16
votes
3 answers

Bootstrapping a Finger Tree Structure

After working with 2-3 finger trees for quite a bit I have been impressed by their speed in most operations. However, the one issue I have run into is the large overhead associated with the initial creation of a large finger tree. Because building…
jbondeson
  • 308
  • 1
  • 6
16
votes
6 answers

Can theoretical computer science be applied in social sciences?

I'm very new to this field - technically not in it but want to be. I'm very early in my academic career (sophomore at a community college) but decided that I want to add a math major along with my computer science major in order to really dive into…
wonderinghuh
  • 369
  • 2
  • 7
16
votes
1 answer

Lower bounds on the size of CFGs for specific finite languages

Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$? We can make the question more interesting by specifying a sequence of languages $L_n$, for example $L_n$ is the set of…
Yuval Filmus
  • 14,445
  • 1
  • 48
  • 92
16
votes
3 answers

Reviewing a paper and found a better solution

I was reviewing a paper of a double-blind conference (ML/AI-based conference). The authors improved the approximation bounds for some special instances of a problem. To understand their proof better, I was thinking of a solution by myself while…
Inuyasha Yagami
  • 1,531
  • 1
  • 8
  • 25
16
votes
3 answers

Any references for techniques in FPT reductions?

As everyone knows, Garey and Johnson's famous book (and many others) provides an excellent reference for reduction technique in classical setting. Are there any surveys or books on the topic of reduction technique in parameterized algorithm, say the…
Regularity
  • 901
  • 5
  • 13
16
votes
4 answers

Algorithms Careers

I’ve been writing software for a living for a number of years now. I have graduate background in mathematics and I am wondering whether knowledge of higher algorithms is utilized anywhere in industry. If so, where, outside of finance? Traditional…
Joe Shmo
  • 301
  • 2
  • 6
16
votes
0 answers

Is this problem on unambiguous finite automata NP-complete?

An unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such that each word has at most one accepting path. In this post, for $n\in \mathbb{N}$, what I call an $n$-UFA (resp., $n$-NFA) is a UFA (resp., NFA) $A$ over…
M.Monet
  • 1,429
  • 7
  • 19
16
votes
2 answers

NLOGTIME versus $\exists$DLOGTIME

$\def\dlt{\mathrm{DLOGTIME}}\def\nlt{\mathrm{NLOGTIME}}\def\mr{\mathrm}$During a recent discussion on another question, I mentioned a factoid $\exists\dlt=\nlt$, but then I realized that I may have misremembered it, as I can’t recall the argument or…
Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
16
votes
2 answers

Publishing short and simple results

I have a manuscript that has been conference-rejected 3 times up to this point. Just to clear things up, I am by no means a senior researcher but I am not a junior who cannot judge the strength of my own work either (I have published in some top…
Proof-From-The-Book
  • 161
  • 3
16
votes
1 answer

Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?

I hope that mathematical logic / recursion theory type questions are welcome here. I am sorry this question is so long and technical, but I believe that if you read it you will find that it is well-motivated. Definitions Let $a \leq_T b$ denote…
Gary Hoppenworth
  • 303
  • 1
  • 8
16
votes
0 answers

Does small circuits for a NP-complete problem contradict ETH?

The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ size, then ETH fails. However, there are no…
Jacobs
  • 161
  • 4
16
votes
7 answers

Mathematical analysis and computational complexity?

computational complexity involves large amounts of Combinatorics and number theory, some ingridiences from stochastics, and an emerging amount of algebra. However, being a analysist, I wonder whether there are applications of analysis into this…
Shoodoon