• Rutgers spelled out in hedges
  • Abstract:

    Information can be digitally encoded (as 0s and 1s) so that even if some of these bits are lost or modified, the information can be recovered. This foundational idea, which is the basis for such commonplace technologies as DVDs and digital broadcast, is explored in theoretical computer science, where it plays a key role in probabilistically checkable proofs and property testing. Exploring the limits of this idea in these abstract settings can lead to new understanding, which enables technological innovation. 

    It has been long known in mathematics that studying the invariances (symmetries) of an object has an important role in understanding the object. In recent years, the study of invariances has led to some significant advances in various topics in theoretical computer science, such as property testing, error-correcting codes and complexity theory. For example, codes with affine invariance and codes with a transitive invariance group have been shown to have important applications in complexity theory, such as constructing PCPs. This project will support the travel of the PIs and their students for research collaborations on these topics with collaborators in Israel. This research will deepen our understanding of objects with invariances, and develop new applications of this theory in complexity theory.

    For more information about the award visit NSF Link

    Please report errors in award information by writing to: .

  • Grant Title: Invariance in error correcting codes and computational complexity
  • Principal Investigator:: Swastik Kopparty
  • Co-Principal Investigator:: Shubhangi Saraf
  • Grant Agency: NSF
  • Grant Duration: 09/01/2016 to 08/31/2019
  • Amount: $40,000

Congratulations to Prof. Swastik Kopparty on winning an NSF CAREER award (NSF 1253886) for his proposal entitled “Error Correcting Codes, Complexity Theory and Pseudorandomness.” The award is effective from February 2013-January 2018.