Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 57 Issue 5, June 2010

Multiobjective A* search with consistent heuristics
Lawrence Mandow, José. Luis Pérez De La Cruz
Article No.: 27
DOI: 10.1145/1754399.1754400

The article describes and analyzes NAMOA*, an algorithm for multiobjective heuristic graph search problems. The algorithm is presented as an extension of A*, an admissible scalar shortest path algorithm. Under consistent...

Polylogarithmic independence fools AC0 circuits
Mark Braverman
Article No.: 28
DOI: 10.1145/1754399.1754401

We prove that poly-sized AC0 circuits cannot distinguish a polylogarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [1990]. The only prior progress on the problem was...

Two-query PCP with subconstant error
Dana Moshkovitz, Ran Raz
Article No.: 29
DOI: 10.1145/1754399.1754402

We show that the NP-Complete language 3Sat has a PCP verifier that makes two queries to a proof of almost-linear size and achieves subconstant probability of error ϵ=o(1). The verifier performs only projection tests, meaning...

Reconciling description logics and rules
Boris Motik, Riccardo Rosati
Article No.: 30
DOI: 10.1145/1754399.1754403

Description logics (DLs) and rules are formalisms that emphasize different aspects of knowledge representation: whereas DLs are focused on specifying and reasoning about conceptual knowledge, rules are focused on nonmonotonic inference. Many...