Reading PAGE

Peer Evaluation activity

Trusted by 1
Downloads 3
Views 25

Total impact ?

    Send a

    Eric has...

    Trusted 2
    Reviewed 0
    Emailed 0
    Shared/re-used 0
    Discussed 0
    Invited 0
    Collected 0

     

    This was brought to you by:

    block this user Eric Allender Trusted member

    Professor

    Dept. of Computer Science, Rutgers University, Piscataway, NJ

    Reducing the complexity of reductions

    Export to Mendeley

    We build on the recent progress regarding isomorphisms of com- plete sets that was reported in Agrawal et al. (1998). In that paper, it was shown that all sets that are complete under (non-uniform) AC0 reductions are isomorphic under isomorphisms computable and invertible via (non-uniform) depth-three AC0 circuits. One of the main tools in proving the isomorphism theorem in Agrawal et al. (1998) is a Gap Theorem, showing that all sets complete under AC0 reductions are in fact already complete under NC0 reduc- tions. The following questions were left open in that paper: 1. Does the gap between NC0 and AC0 extend further? In particular, is every set complete under polynomial-time reducibility already complete under NC0 reductions? 2. Does a uniform version of the isomorphism theorem hold? 3. Is depth-three optimal, or are the complete sets isomorphic under iso- morphisms computable by depth-two circuits? We answer all of these questions. In particular, we prove that the Berman Hartmanis isomorphism conjecture is true for P-uniform AC0 reductions. More precisely, we show that for any class C closed under uniform TC0 -computable many-one reductions, the following three theorems hold: 1. If C contains sets that are complete under a notion of reduction at least as strong as Dlogtime-uniform AC0 mod 2 reductions, then there are such sets that are not complete under (even non-uniform) AC0 reductions. 2. The sets complete for C under P-uniform AC0 reductions are all isomor- phic under isomorphisms computable and invertible by P-uniform AC0 circuits of depth-three. 3. There are sets complete for C under Dlogtime-uniform AC0 reductions that are not isomorphic under any isomorphism computed by (even non- uniform) AC0 circuits of depth two. To prove the second theorem, we show how to derandomize a version of the switching lemma, which may be of independent interest. (We have recently learned that this result is originally due to Ajtai and Wigderson, but it has not been published.)

    Oh la laClose

    Your session has expired but don’t worry, your message
    has been saved.Please log in and we’ll bring you back
    to this page. You’ll just need to click “Send”.

    Your evaluation is of great value to our authors and readers. Many thanks for your time.

    Review Close

    Short review
    Select a comment
    Select a grade
    You and the author
    Anonymity My review is anonymous( Log in  or  Register )
    publish
    Close

    When you're done, click "publish"

    Only blue fields are mandatory.

    Relation to the author*
    Overall Comment*
    Anonymity* My review is anonymous( Log in  or  Register )
     

    Focus & Objectives*

    Have the objectives and the central topic been clearly introduced?

    Novelty & Originality*

    Do you consider this work to be an interesting contribution to knowledge?

    Arrangement, Transition and Logic

    Are the different sections of this work well arranged and distributed?

    Methodology & Results

    Is the author's methodology relevant to both the objectives and the results?

    Data Settings & Figures

    Were tables and figures appropriate and well conceived?

    References and bibliography

    Is this work well documented and has the bibliography been properly established?

    Writing

    Is this work well written, checked and edited?

    Write Your Review (you can paste text as well)
    Please be civil and constructive. Thank you.


    Grade (optional, N/A by default)

    N/A 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9 9.5 10
    Close

    Your mailing list is currently empty.
    It will build up as you send messages
    and links to your peers.

     No one besides you has access to this list.
    Close
    Enter the e-mail addresses of your recipients in the box below.  Note: Peer Evaluation will NOT store these email addresses   log in
    Your recipients

    Your message:

    Your email : Your email address will not be stored or shared with others.

    Your message has been sent.

    Description

    Title : Reducing the complexity of reductions
    Author(s) : Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
    Abstract : We build on the recent progress regarding isomorphisms of com- plete sets that was reported in Agrawal et al. (1998). In that paper, it was shown that all sets that are complete under (non-uniform) AC0 reductions are isomorphic under isomorphisms computable and invertible via (non-uniform) depth-three AC0 circuits. One of the main tools in proving the isomorphism theorem in Agrawal et al. (1998) is a Gap Theorem, showing that all sets complete under AC0 reductions are in fact already complete under NC0 reduc- tions. The following questions were left open in that paper: 1. Does the gap between NC0 and AC0 extend further? In particular, is every set complete under polynomial-time reducibility already complete under NC0 reductions? 2. Does a uniform version of the isomorphism theorem hold? 3. Is depth-three optimal, or are the complete sets isomorphic under iso- morphisms computable by depth-two circuits? We answer all of these questions. In particular, we prove that the Berman Hartmanis isomorphism conjecture is true for P-uniform AC0 reductions. More precisely, we show that for any class C closed under uniform TC0 -computable many-one reductions, the following three theorems hold: 1. If C contains sets that are complete under a notion of reduction at least as strong as Dlogtime-uniform AC0 mod 2 reductions, then there are such sets that are not complete under (even non-uniform) AC0 reductions. 2. The sets complete for C under P-uniform AC0 reductions are all isomor- phic under isomorphisms computable and invertible by P-uniform AC0 circuits of depth-three. 3. There are sets complete for C under Dlogtime-uniform AC0 reductions that are not isomorphic under any isomorphism computed by (even non- uniform) AC0 circuits of depth two. To prove the second theorem, we show how to derandomize a version of the switching lemma, which may be of independent interest. (We have recently learned that this result is originally due to Ajtai and Wigderson, but it has not been published.)
    Subject : unspecified
    Area : Other
    Language : English
    Year : 1997

    Affiliations Dept. of Computer Science, Rutgers University, Piscataway, NJ
    Journal : Proceedings of the twentyninth annual ACM symposium on Theory of
    Volume : 10
    Issue : 2
    Publisher : ACM Press
    Pages : 730-738
    Url : http://portal.acm.org/citation.cfm?doid=258533.258671
    Doi : 10.1145/258533.258671

    Leave a comment

    This contribution has not been reviewed yet. review?

    You may receive the Trusted member label after :

    • Reviewing 10 uploads, whatever the media type.
    • Being trusted by 10 peers.
    • If you are blocked by 10 peers the "Trust label" will be suspended from your page. We encourage you to contact the administrator to contest the suspension.

    Does this seem fair to you? Please make your suggestions.

    Please select an affiliation to sign your evaluation:

    Cancel Evaluation Save

    Please select an affiliation:

    Cancel   Save

    Eric's Peer Evaluation activity

    Trusted by 1
    Downloads 3
    Views 25

    Eric has...

    Trusted 2
    Reviewed 0
    Emailed 0
    Shared/re-used 0
    Discussed 0
    Invited 0
    Collected 0
    Invite this peer to...
    Title
    Start date (dd/mm/aaaa)
    Location
    URL
    Message
    send
    Close

    Full Text request

    Your request will be sent.

    Please enter your email address to be notified
    when this article becomes available

    Your email


     
    Your email address will not be shared or spammed.