Alessandro Cosentino
  • Member for 11 years, 4 months
  • Last seen this week
What are the recent TCS books whose drafts are available online?
37 votes

Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani EDIT (Sept 16 '15): The link is broken, I believe the draft is no longer available online.

View answer
Problem in BPP but not known to be in RP or co-RP
Accepted answer
22 votes

Moved my comment here after Suresh's request. An example of a natural problem for which we only know algorithms that require error on both sides is the following: given three algebraic circuits, ...

View answer
Reading up on $BQP = BPP^{BQNC}$
Accepted answer
20 votes

This was conjectured by R. Jozsa in Section 8 of arXiv:quant-ph/0508124. If you are already familiar with quantum computing and quantum complexity theory, you can start by reading that section. An ...

View answer
How important is knowing how to program for TCS?
19 votes

Three points: 1) There is an approach to mathematics called Experimental Mathematics (see also wikipedia://Computer-aided proof) where you use computer programs to investigate about patterns and ...

View answer
A good reference for complexity class operators?
Accepted answer
18 votes

Here is a reference with many definitions of operators (not many details though): S. Zachos and A. Pagourtzis, Combinatory Complexity: Operators on Complexity Classes, Proceedings of 4th ...

View answer
Communication Complexity ...Classes?
16 votes

A section of the Complexity Zoo lists the most important Communication Complexity classes.

View answer
Advice on good research practices
15 votes

Richard Feynman's must-read book "Surely You're Joking, Mr. Feynman!" is a mine of good research practices. My favorite Feynman's advice is on how teaching helps to do good research, see these ...

View answer
Is there a quantum NC algorithm for computing GCD?
Accepted answer
14 votes

First of all, there is a formal definition of "quantum-NC", see QNC on the zoo. GCD is indeed a good candidate for a problem that could be shown to be in QNC, but it's not known to be in NC. However, ...

View answer
Is $PH \subseteq PP$?
13 votes

Something that has not been mentioned so far (as far as I can see) and that holds in the unrelativized world is the following: $$PH \subseteq PP \quad\mbox{ if }\quad QMA = PP.$$ This was observed ...

View answer
Applications of topology to computer science
12 votes

All the work started by Kitaev on the topological approach to a fault tolerant quantum computer. See Kitaev's original paper or, for example, John Preskill's lecture notes.

View answer
Fast Reduction from RSA to SAT
10 votes

ToughSat by Henry Yuen and Joseph Bebel is another tool similar to the one linked by @Martin, which generates CNF formulas that encode instances of factoring and other hard problems.

View answer
Parity and $AC^0$
10 votes

1) The first that comes to my mind is MAJORITY. You can prove that it is not in $AC^{0}$ with the same techniques. See Håstad's thesis for details. 2) A topological approach, again working only for ...

View answer
Factoring as a decision problem
9 votes

Yes, there is a paper by John Watrous, which formally addresses the concerns raised on Lipton's blog (reported in user2917198's comment). Here is the reference: J. Watrous. An introduction to quantum ...

View answer
Upperbound on the degree of a boolean function in terms of its sensitivity
9 votes

This paper came up on the arXiv today and it improves on the upper bound on $bs(f)$ in terms of $s(f)$. They prove the following bound: $$ bs(f) \leq 2^{s(f)-1}s(f). $$ This along with the ...

View answer
Books on programming language semantics
9 votes

I really enjoyed reading Winskel when I was taking the undergrad course on semantics. I can't tell if it's dated, though, since I don't do research in this field. A plus of Winskel is that you can ...

View answer
Oracle results on P vs BPP
8 votes

A nice description of an oracle that separates P and BPP is given by Greg Kuperberg in one of the comments of this interesting blog post, where Terence Tao describes Turing machines with oracles and ...

View answer
Quantum proofs of classical theorems
8 votes

Two very recent and interesting results: Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf proved that "there exists no polynomial-size linear program (LP) whose ...

View answer
What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?
7 votes

Something you might be interested in is the notion of quantum oracle introduced by Aaronson and Kuperberg in arXiv:quant-ph/0604056. Quoting from their paper: Just as a classical oracle models a ...

View answer
Can we quantify the "degree of quantumness" in a quantum algorithm ?
7 votes

A more complexity theoretical point of view can be found in Sec. 8 of R. Josza's paper An introduction to measurement based quantum computation. He states the following: The measurement based ...

View answer
List of quantum-inspired algorithms
Accepted answer
6 votes

As claimed by Leslie G. Valiant in a seminal paper 1 of his, Holographic algorithms are inspired by the quantum computational model. However, they are executable on classical computers and do not ...

View answer
Quantum PCP and hardness of simulating of Hamiltonians
6 votes

Basically everything that is known about the Quantum PCP conjecture has been collected in this survey by Dorit Aharonov, Itai Arad, and Thomas Vidick: The Quantum PCP Conjecture See also Thomas' ...

View answer
Known properties of a specific class of quantum states
6 votes

M. G. Parker and V. Rijmen have studied the quantum entanglement of binary and bipolar sequences in arXiv:quant-ph/0107106. I remember reading their paper long ago. They use a lot of terminology from ...

View answer
What tools do you use to give presentations?
5 votes

Something that is not well known and used in academia yet is http://prezi.com/ It's a completely online tool to create presentations. Basically it's a cool way to navigate a poster. In my opinion it'...

View answer
Bounding the gap between quantum and deterministic query complexity
3 votes

A lot of progress has been made on this question in 2015. First, in arXiv:1506.04719 [cs.CC], the authors have improved on the quadratic separation by showing a total function $f$ with $$ Q(f) = \...

View answer
Complexity class for quantum computer with commutative gates
Accepted answer
3 votes

There isn't a one word answer to your question, but you can have a look at Xiaotong Ni's master thesis, where commuting circuits with several restrictions are considered and compared to classical ...

View answer