Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
18
votes
0 answers

Complexity of the densest $k$-subgraph problem on planar graphs

In the densest $k$-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is maximized. The subgraph is not required to be…
Aaron Schild
  • 367
  • 1
  • 9
18
votes
1 answer

The complexity of sampling (approximately) the Fourier transform of a Boolean function

One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P. Here and below when I talk about sampling the Fourier…
Gil Kalai
  • 6,033
  • 35
  • 73
18
votes
1 answer

What is the categorical semantics of subtyping?

Starting from Curry-Howard-Lambek, there has been a nice trinity of type theories, logics, and categories. I'm curious what categorical semantics you get when you add (coercive) subtyping to a type theory -- it seems like this has not been explored…
Darius Jahandarie
  • 313
  • 1
  • 8
18
votes
3 answers

Constructively efficient algorithms without efficient correctness and efficiency proof

I am looking for natural examples of efficient algorithms (i.e. in polynomial time) s.t. their correctness and efficiency can be proven constructively (e.g. in $PRA$ or $HA$), but no proof using only efficient concepts is known (i.e. we don't know…
Kaveh
  • 21,577
  • 8
  • 82
  • 183
18
votes
1 answer

Is induced subgraph isomorphism easy on an infinite subclass?

Is there a sequence of undirected graphs $\{C_n\}_{n\in \mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$? is known to be in class $\mathsf{P}$? (For example,…
sdcvvc
  • 1,291
  • 9
  • 19
18
votes
3 answers

funsplit and polarity of Pi-types

In a recent thread on the Agda mailing list, the question of $\eta$ laws popped up, in which Peter Hancock made thought-provoking remark. My understanding is that $\eta$ laws come with negative types, ie. connectives which introduction rules are…
pedagand
  • 478
  • 2
  • 6
18
votes
2 answers

Status on circuit lower bounds for polylog-bounded depth circuits

Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ function is not computed by $AC^{0}[q]$", where…
shen
  • 279
  • 1
  • 4
18
votes
0 answers

$\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$?

Assuming $\mathsf{P} \ne \mathsf{NP}$ can we show $\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$? Obviously this would be the case if $\mathsf{P} \ne \mathsf{NP}$ and $\mathsf{P/poly} \supset \mathsf{NP}$ but this is unlikely. This is also true…
Vanessa
  • 2,151
  • 12
  • 21
18
votes
7 answers

Pointers for CS applications of logic

I'm a grad student in math with a solid background in logic. I've taken a year-long graduate course in logic together with graduate courses on finite model theory and another on forcing and set theory. Most CS texts seem to assume only a very modest…
evf
  • 81
  • 3
18
votes
1 answer

Polynomial speedups with algorithms based on semidefinite programming

This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time. I am still puzzling over the actual running time of algorithms that compute the solution of a semidefinite program (SDP). As Robin pointed…
Alessandro Cosentino
  • 4,000
  • 35
  • 43
18
votes
2 answers

The motivation for using Karp-reductions in the theory of $\mathcal{NP}$-completeness

The notion of polynomial time reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using an algorithm for a different problem. However, in the theory of $\mathcal{NP}$-completeness, the notion…
Belle
  • 725
  • 5
  • 9
18
votes
1 answer

What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?

What is the best deterministic result for maintaining the dynamic transitive closure in a directed graph with only edge insertion? I read some papers on the dynamic transitive closure problem with both edge insertion and deletion. However, is there…
wei wang
  • 519
  • 2
  • 7
18
votes
2 answers

Is it possible to decide $\beta$-equivalence within System F (or another normalizing typed λ-calculus)?

I know that's impossible to decide $\beta$-equivalence for untyped lambda calculus. Quoting Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics. North Holland, Amsterdam (1984).: If A and B are disjoint, nonempty sets of lambda terms…
Petr
  • 2,601
  • 15
  • 28
18
votes
3 answers

Frame rule as a change-preserver?

A frame rule, like the one given below, captures the idea that, given a program c with precondition p that holds before it runs and postcondition q that holds afterward, some disjoint condition r should hold both before and after c runs. (The *…
Lindsey Kuper
  • 323
  • 1
  • 6
18
votes
2 answers

Is there a theory that combines category theory/abstract algebra and computational complexity?

Category theory and abstract algebra deal with the way functions can be combined with other functions. Complexity theory deals with how hard a function is to compute. It's weird to me that I haven't seen anyone combine these fields of study, since…
Mike Izbicki
  • 1,073
  • 7
  • 15
1 2 3
…
99 100