Attempts at classifying computational problems as polynomial time
solvable, NP-complete, or belonging to a higher level in the polynomial
hierarchy, face the difficulty of undecidability. These classes, including
NP, admit a logic formulation. By suitably restricting the formulation, one
finds the logic class MMSNP, or monotone monadic strict NP without
more >>>

We present three new quantum hardcore functions for any quantum one-way function. We also give a "quantum" solution to Damgard's question (CRYPTO'88) on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.
Our technical tool is ... more >>>

Recently Bansal and Sviridenko (Proc. of the 15th SODA'04, 189-196)
proved that for
2-dimensional Orthogonal Rectangle
Bin Packing without rotations allowed there is no asymptotic PTAS, unless P=NP. We show that similar
approximation hardness results hold for several rectangle packing and covering problems even if rotations by ninety
more >>>