All Questions

Filter by
Sorted by
Tagged with
54 votes
21 answers
4k views

Dinner-table description of theoretical computer science?

I'm often asked what a theoretical computer scientist does. It would be great to have some nice responses to this question. I tend to fall back to technical jargon and people's eyes usually glaze ...
30 votes
4 answers
3k views

Why do we need formal semantics for predicate logic?

Consider this question solved. I will not pick a best answer as all of them have contributed to my understanding of the topic. Im unsure what benefit we have by formally defining the semantics of ...
Martin's user avatar
  • 309
14 votes
2 answers
498 views

Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model

In a paper titled "On Deniability in the Common Reference String and Random Oracle Model," Rafael Pass writes: We note that when proving security according to the standard zero-knowledge ...
Sadeq Dousti's user avatar
  • 16.5k
9 votes
2 answers
812 views

Understanding QMA

This question comes out of an answer Joe Fitzsimons gave to a different question. Most natural complexity classes have a one-line "intuitive description" that helps characterize core problems in that ...
Suresh Venkat's user avatar
17 votes
2 answers
747 views

Hardness of parameterized CLIQUE?

Let $0\le p\le 1$ and consider the decision problem CLIQUE$_p$ Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges Question: does $G$ contain a clique on at ...
András Salamon's user avatar
5 votes
1 answer
232 views

How can one construct a densest graph with no k-clique?

Given integers $k$ and $n$ with $2 \le k < n$, how does one construct a graph on $n$ vertices that contains no $k$-clique and has the maximal number of edges? This sounds like basic ...
András Salamon's user avatar
8 votes
1 answer
515 views

Algorithms and computational complexity of clique and biclique covers

I've been reading a paper by a mathematical chemist. He proposes some indices to measure the complexity of molecules. From here on in, instead of molecules, think undirected connected graphs: a ...
Aaron Sterling's user avatar
15 votes
10 answers
3k views

Intractability of NP-complete problems as a principle of physics?

I'm always intrigued by the lack of numerical evidence from experimental mathematics for or against the P vs NP question. While the Riemann Hypothesis has some supporting evidence from numerical ...
Mohammad Al-Turkistany's user avatar
7 votes
3 answers
664 views

Best sources on data stream algorithms

I recently got interested in data stream algorithms to the point that I'd like to study the topic and then teach it to someone. I'd be thus grateful for pointers to really good sources on the topic, ...
jkff's user avatar
  • 8,971
5 votes
2 answers
4k views

What are the main sub-areas of theoretical computer science?

I often want to give students a broad view of theoretical computer science, in the beginning of algorithms class or when advising a new student. It is hard for me to decide which sub-areas to talk ...
30 votes
7 answers
25k views

Why is CNF used for SAT and not DNF?

I don't quite understand why almost all SAT solvers use CNF instead of DNF. It seems to me that solving SAT is easier using DNF. After all, you just have to scan through the set of implicants and ...
user avatar
10 votes
3 answers
580 views

Is embedding a solution feasible for SAT?

I am interested in "hard" individual instances of NP-complete problems. Ryan Williams discussed the SAT0 problem at Richard Lipton's blog. SAT0 asks whether a SAT instance has the specific solution ...
András Salamon's user avatar
15 votes
2 answers
516 views

Are there intermediate eta theories for the lambda calculus?

There are two main, studied theories of the lambda calculus, the beta theory and its Post-complete extension, the beta-eta theory. Do these two theories have an in-between, a kind of intermediate eta ...
Charles Stewart's user avatar
5 votes
1 answer
2k views

PAC learning boolean conjunctions

Kearns and Vazirani (chapter 1) describe an efficient algorithm for PAC learning conjunctions of boolean variables $x_1, x_2, \ldots, x_n$, which starts with the hypothesis $$h=x_1\wedge\overline{x_1}\...
Anthony Labarre's user avatar
13 votes
2 answers
697 views

One-shot quantum hitting times

In the paper Quantum Random Walks Hit Exponentially Faster (arXiv:quant-ph/0205083) Kempe gives a notion of hitting time for quantum walks (in the hypercube) that is not very popular in the quantum ...
Marcos Villagra's user avatar
12 votes
1 answer
601 views

Positive topological ordering, take 2

This is a followup to David Eppstein's recent question and is motivated by the same problems. Suppose I have a dag with real-number weights on its vertices. Initially, all of the vertices are ...
Jeffε's user avatar
  • 23.2k
16 votes
1 answer
612 views

Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

This is a follow up to this question, and is related to this question of Shiva Kinali. It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use ...
Kaveh's user avatar
  • 21.7k
25 votes
4 answers
3k views

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 ...
Shiva Kintali's user avatar
5 votes
4 answers
302 views

Find a function that combines a set of integers and outputs an integer. This output can be used to deduce the absence of any integer in the set.

Lets say that I have 50 events that generate some unique number (you are free to choose the number, but they should all fit in a 32 bit variable). I want to combine those numbers into a single number(...
Sridhar Iyer's user avatar
7 votes
1 answer
263 views

Is it possible to model maximization in a petri net without using inhibitor arcs?

Creating a petri-net that models the minimum function is quite simple: ...
Heinzi's user avatar
  • 173
16 votes
3 answers
372 views

Are there any classes of functions which require provably different resources to compute versus computing their inverse?

Apologies in advance if this question is too simple. Basically, what I want to know is if there are any functions $f(x)$ with the following properties: Take $f_n(x)$ to be $f(x)$ when the domain and ...
Joe Fitzsimons's user avatar
52 votes
3 answers
6k views

Shallow versus Deep Embeddings

When encoding a logic into a proof assistant such as Coq or Isabelle, a choice needs to be made between using a shallow and a deep embedding. In a shallow embedding logical formulas are written ...
Dave Clarke's user avatar
  • 16.7k
7 votes
2 answers
463 views

Optimizing $\epsilon$ in $\epsilon$-kernel

The notion of $\epsilon$-kernel, as defined by Agarwal et al. ("Approximating extent measures of points"), is the following. Let $S^{d−1}$ denote the unit sphere centered at the origin in $R^d$. For ...
Danu's user avatar
  • 763
9 votes
1 answer
471 views

In System F à la Church, can we automatize type inference for the for-all elimination?

The question is the following. Generally when one have a term like $\Lambda X.t$, we can eliminate the forall by applying this term to a type, as instance $(\Lambda X.t)[T]\to t[X:=T]$. Now, suppose ...
Alejandro DC's user avatar
9 votes
5 answers
455 views

Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results

Are there any known results showing that existence (or non-existence) of finite graphs with specific computable properties imply certain complexity results (such as P = NP)? Here's one completely ...
Ajay's user avatar
  • 147
6 votes
4 answers
1k views

Distributed Elections using Logical Clocks (hints and tips)

I need to implement one of the logical clock algorithms (described here), to allow me to coordinate an election protocol for a distributed system. I'm struggling to work out how I might go about using ...
Andrew Matthews's user avatar
5 votes
2 answers
389 views

Use of Lagrangian dual information to prove optimalitiy of a solution : Any example?

Can anyone please tell me what is Lagrangian Dual Information and how can it be used to prove the optimality of a solution? I'm talking about the solution to NP-Complete problems. Is it something that ...
user avatar
12 votes
2 answers
3k views

Does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable?

I believe the answer to this question is well-known; but, unfortunately, I don't know. In quantum computing, we know that mixed states are represented by density matrices. And the trace norm of the ...
Jeremy Yan's user avatar
47 votes
5 answers
3k views

Positive topological ordering

Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of ...
David Eppstein's user avatar
24 votes
1 answer
890 views

Logspace algorithms on graphs with bounded tree width

Tree width measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known approximation algorithm achieves $O(\sqrt{{\log}n})$ factor. Courcelle's theorem states that ...
Shiva Kintali's user avatar
2 votes
1 answer
285 views

Number of Vertex Covers and Permanent

Is there any relationship between the number of vertex covers of a graph $G$ and the permanent of $G$'s adjacency matrix?
Giorgio Camerani's user avatar
10 votes
1 answer
538 views

What are the theoretical limits of the Stratego Programming Language?

Stratego is a programming transformation language/Rewriting DSL. Anthony Sloane has done some work doing an implementation that runs on Scala. What are the theoretical limits of Stratego as a ...
hawkeye's user avatar
  • 2,581
20 votes
2 answers
7k views

Algorithm for 'k'' most frequently occurring numbers

I have been searching for the most efficient (streaming??) algorithm that tells me the 'k' most frequently occurring elements in a data stream at any point in time. This post: "Divide and conquer&...
dhruvbird's user avatar
  • 460
20 votes
2 answers
965 views

Problems between NC and P: How many have been resolved from this list?

In the paper "A Compendium of Problems Complete for P" by Greenlaw, Hoover and Ruzzo (PS) (PDF), there is a list of problems in P that are not known to be in NC and not known to be P-complete either. (...
Robin Kothari's user avatar
24 votes
1 answer
3k views

Space complexity of Coppersmith–Winograd algorithm

Coppersmith–Winograd algorithm is the asymptotically fastest known algorithm for multiplying two $n \times n$ square matrices. The running time of their algorithm is $O(n^{2.376})$ which is the best ...
Shiva Kintali's user avatar
7 votes
1 answer
320 views

Property testing of triangular properties

Several years ago I worked a few days with a collaborator on property testing of triangular property. We end up with a disappointing result that I am sharing here and for which I am asking if a better ...
Sylvain Peyronnet's user avatar
10 votes
2 answers
493 views

Consequences of lower bounds for $\epsilon$-nets on approximation

Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF]. I would like to know what, if anything, such a lower bound implies ...
James King's user avatar
  • 2,633
28 votes
2 answers
1k views

Approximate counting problem capturing BQP

In the black-box model, the problem of determining the output of a BPP machine $M(x,r)$ on input $x$ is the approximate counting problem of determining $E_r M(x,r)$ with additive error 1/3 (say). Is ...
Manu's user avatar
  • 7,669
8 votes
2 answers
3k views

Monotone-2SAT and Vertex Cover

The following decision problem is called k-True-Monotone-2SAT: Given a 2-CNF boolean formula $F$ that does not contain any negated variables and given a positive integer $k$, can $F$ be satisfied ...
Giorgio Camerani's user avatar
11 votes
2 answers
3k views

Integer Factoring via Lattice Reduction?

I found a paper titled "Factoring integers and computing discrete logarithms via diophantine approximation" by C. P. Schnorr from 1993. It looks like a probabilistic method with expected polynomial ...
user834's user avatar
  • 2,806
24 votes
3 answers
1k views

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
Jason's user avatar
  • 241
21 votes
10 answers
3k views

#SAT Solver download

Could anyone please point to one or more websites where is possible to download a working implementation of a #SAT solver? I'm interested in those returning the exact solution count, not an ...
Giorgio Camerani's user avatar
12 votes
6 answers
2k views

"Divide and conquer" data stream algorithms

What useful algorithms do there exist that work on huge data streams and also their results are fairly small and one can compute the result for a mixture of two streams by somehow merging their ...
jkff's user avatar
  • 8,971
4 votes
1 answer
4k views

2D Cutting Stock Problem for Glass - Details mentioned

I am trying to work on Cutting Stock Problem. I have seen some algorithm. Can anybody suggest the best 2D cutting stock problem algorithm? I am looking for kind of best acceptable solution for 2D ...
Sandeep Jindal's user avatar
2 votes
2 answers
3k views

Graph encoding algorithms that you know of ?

Is there any compilation of graph encoding algorithms? I know about Prufer and Huffman encoding. But papers say, prufer is not good enough to represent Minimum Spanning Trees in the sense it may ...
16 votes
1 answer
887 views

LogDCFL-complete problems

LogCFL is the set of all languages that are logspace reducible to a context-free language. Similarly, LogDCFL is the set of all languages that are logspace reducible to a deterministic context-free ...
Shiva Kintali's user avatar
65 votes
5 answers
2k views

Problems that can be used to show polynomial-time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
Robin Kothari's user avatar
1 vote
1 answer
542 views

Complexity of two perfect matchings with minimum shared edges?

Perfect Matching problem is polynomial time solvable in general graphs. Given undirected simple graph, Is the problem of finding two perfect matching with minimum shared edges between them ...
Mohammad Al-Turkistany's user avatar
2 votes
2 answers
2k views

polygonal triangulation and 3-colorability

Lets define polygonal triangulation a triangulation which has a hamiltonian cycle. It's easy to see that any polygonal triangulation is 3-colorable since any triangulation of a polygon is 3-colorable....
ptigas's user avatar
  • 43
22 votes
2 answers
2k views

Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, ...

15 30 50 per page
1
252 253
254
255 256
261