skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions
Award ID(s):
2127597
PAR ID:
10392781
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Bakay, Özge; Pratley, Breanna; Neu, Eva; Deal, Peyton (Ed.)
    The existence and nature of abstract Case has been debated in recent years (McFadden 2004, Landau 2006, Markman 2009), particularly in languages that show no morphological case marking (Diercks 2012, Sheehan & van der Wal 2016). Using data from original fieldwork, I argue that Nukuoro (Polynesian-Outlier) instantiates abstract ergative Case without morphological case or agreement. Nukuoro shows a range of syntactic phenomena indicative of abstract Case, including object shift and pseudo noun incorporation (e.g., Massam 2001), syntactic ergativity in A'-movement, and alternative licensing in tenseless clauses. This pattern provides support for modern theories of Case (Legate 2008), which cleave the assignment of abstract Case from its realization in the morphology; additionally, this pattern differs from other documented examples of unrealized abstract Case by having an ergative alignment, rather than a nominative one (Halpert 2016, Sheehan & van der Wal 2016). 
    more » « less