Most Popular
1500 questions
16
votes
1 answer
Making a minimum-width tree decomposition lean in polynomial time
As is well known, a tree decomposition of a graph $G$ consists of a tree $T$ with an associated bag $T_v \subseteq V(G)$ for each vertex $v \in V(T)$, which satisfies the following conditions:
Every vertex of $G$ occurs in some bag of $T$.
For…
Bart Jansen
- 5,265
- 21
- 39
16
votes
2 answers
Number of binary gates needed to compute AND and OR of n input bits simultaneously
What is the minimal number of binary gates needed to compute AND and OR of $n$ input bits simultaneously?
The trivial upper bound is $2n-2$. I believe that this is optimal, but how to prove this? The standard
gate elimination technique does not…
Alexander S. Kulikov
- 895
- 5
- 11
16
votes
4 answers
Definition of matrix-multiplication exponent $\omega$
Colloquially, the definition of the matrix-multiplication exponent $\omega$ is the smallest value for which there is a known $n^{\omega}$ matrix-multiplication algorithm. This is not acceptable as a formal mathematical definition, so I guess the…
David Harris
- 3,488
- 22
- 24
16
votes
3 answers
Graduate studies (PhD) in CS Theory vs. Applied Math
Given most American universities only accept applications in only one field, I'm trying to figure out what are the advantages/disadvantages of applying to a CS theory program vs an applied math program given one's interest lies somewhere in both…
user972432
- 303
- 1
- 2
- 7
16
votes
3 answers
Can we prove weak normalization for System F by induction on a transfinite ordinal
Weak normalization for the simple typed lambda calculus can be proved (Turing) by induction on $\omega^2$. An extended lambda calculus with recursors on natural numbers (Gentzen) has a weak normalization strategy by induction on $\epsilon_0$.
What…
user6892
16
votes
4 answers
When are more publications less?
Are there cases where extra publications can hurt your record?
This is avoiding the obvious cases where you publish incorrect, or controversial results. Also avoiding the case of finite-time: you only have so much time to think and write, so…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
16
votes
1 answer
Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME?
Is the following problem in PTIME, or coNP-hard:
Given two Boolean expressions $e_1$ and $e_2$ in variables $x_1,\dots,x_n$, without negation (ie, the expressions are entirely built up via $\wedge$ and $\vee$). Decide whether $e_1 \equiv e_2$, that…
danielzinn
- 288
- 1
- 6
16
votes
2 answers
Paradigms for complexity analysis of algorithms
Worst-case and average case analysis are well-known measures for the complexity of an algorithm. Recently smoothed analysis has emerged as another paradigm to explain why some algorithms which are exponential in the worst-case work so well in…
Opt
- 1,311
- 14
- 20
16
votes
6 answers
Quantum computing project ideas
I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?
Deyaa
- 544
- 7
- 14
16
votes
1 answer
Seeking Scott's original LCF paper
Is the following manuscript publically available?
Dana Scott, 1969, A theory of computable functions of higher type. Unpublished seminar notes, 7 pages, University of Oxford.
There is a discussion of this paper in section 8.1.2, Types as sets, in…
Charles Stewart
- 4,316
- 28
- 45
16
votes
2 answers
Quantum PAC learning
Background
Functions in $AC^0$ are PAC learnable in quasipolynomial time with a classical algorithm that requires $O(2^{log(n)^{O(d)}})$ randomly chosen queries to learn a circuit of depth d [1]. If there is no $2^{n^{o(1)}}$ factoring algorithm…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
16
votes
2 answers
Complexity class corresponding to sorting
Two parts of TCS are algorithms and complexity. I'll simplistically say that algorithms is the study of upper bounds, showing that you can do something (with given restricted resources), and complexity is about showing that you cannot do it without…
Mitch
- 905
- 8
- 19
16
votes
2 answers
Hard Instances for graph isomorphism testing
Is the case of strongly regular graphs
the hardest one for GI testing?
where "hardest" is used in some "common sense" meaning, or "in average", so to speak.
Wolfram MathWorld mentions some "pathologically hard graphs". What are they?
My sample…
trg787
- 479
- 4
- 11
16
votes
2 answers
What is the fastest algorithm to compute rank of a rectangular matrix?
Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns?
I am aware it can be solved through linear matroid intersection, which implies
an $O(mn^{1.62})$ time deterministic…
Ho Yee Cheung
- 163
- 2
- 8
16
votes
3 answers
Is there any programming language theory describing foreign function interfaces (FFI) and multiple language bindings?
Is there any programming language theory describing foreign function interfaces (FFI) and multiple language bindings?
I have asked some implementation issues on stackoverflow, which is not suitable here. But I would like to ask from this site's…
Tim
- 639
- 3
- 15