Please wait, while we are loading the content...
Please wait, while we are loading the content...
| Content Provider | Springer Nature Link |
|---|---|
| Author | Wang, LiWei Zhang, JiaPeng |
| Copyright Year | 2015 |
| Abstract | Differentially private query answering is an important problem in machine learning and data analysis. As an example, the users may want to know the empirical errors of some classifiers on a training data set which contains sensitive information. In this case, the answers returned by the database holder must preserve privacy. Previous results show that answering large number of queries with differential privacy is computationally expensive. However, almost all the hardness results are conditional, which means that they rely on unproved conjectures. One exception is the hardness for stateless mechanisms, in which the sanitizer is assumed to have very limited memory and can only answer the queries separately. In this work, we explore the hardness for differentially private query answering mechanisms beyond the stateless restriction. Specifically, we investigate the measurement complexity of a natural class of stateful sanitizer. Here, measurement refers to the evaluation of a query (a Boolean function) on a data point. Measurement complexity is a lower bound for the running time. We prove unconditional subexponential lower bound for the measurement complexity of the class of sanitizer with ɛ-differential privacy. Possible generalization of the results is also discussed.差分隐私的计算复杂度. 通过定义并研究所谓测量复杂度, 对于一大类算法 (包括目前已知的差分隐私算法) 给出了不基于其它未证明猜想的复杂度下界. 指出了对于任意算法差分隐私的测量复杂度下界与 P vs NP 问题的关系. |
| Starting Page | 1 |
| Ending Page | 11 |
| Page Count | 11 |
| File Format | |
| ISSN | 1674733X |
| Journal | Science in China Series : Information Sciences |
| Volume Number | 58 |
| Issue Number | 9 |
| e-ISSN | 18691919 |
| Language | Chinese |
| Publisher | Science China Press |
| Publisher Date | 2015-07-03 |
| Publisher Place | Beijing |
| Access Restriction | One Nation One Subscription (ONOS) |
| Subject Keyword | privacy differential privacy query measurement complexity learning Information Systems and Communication Service |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
National Digital Library of India (NDLI) is a virtual repository of learning resources which is not just a repository with search/browse facilities but provides a host of services for the learner community. It is sponsored and mentored by Ministry of Education, Government of India, through its National Mission on Education through Information and Communication Technology (NMEICT). Filtered and federated searching is employed to facilitate focused searching so that learners can find the right resource with least effort and in minimum time. NDLI provides user group-specific services such as Examination Preparatory for School and College students and job aspirants. Services for Researchers and general learners are also provided. NDLI is designed to hold content of any language and provides interface support for 10 most widely used Indian languages. It is built to provide support for all academic levels including researchers and life-long learners, all disciplines, all popular forms of access devices and differently-abled learners. It is designed to enable people to learn and prepare from best practices from all over the world and to facilitate researchers to perform inter-linked exploration from multiple sources. It is developed, operated and maintained from Indian Institute of Technology Kharagpur.
Learn more about this project from here.
NDLI is a conglomeration of freely available or institutionally contributed or donated or publisher managed contents. Almost all these contents are hosted and accessed from respective sources. The responsibility for authenticity, relevance, completeness, accuracy, reliability and suitability of these contents rests with the respective organization and NDLI has no responsibility or liability for these. Every effort is made to keep the NDLI portal up and running smoothly unless there are some unavoidable technical issues.
Ministry of Education, through its National Mission on Education through Information and Communication Technology (NMEICT), has sponsored and funded the National Digital Library of India (NDLI) project.
| Sl. | Authority | Responsibilities | Communication Details |
|---|---|---|---|
| 1 | Ministry of Education (GoI), Department of Higher Education |
Sanctioning Authority | https://www.education.gov.in/ict-initiatives |
| 2 | Indian Institute of Technology Kharagpur | Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project | https://www.iitkgp.ac.in |
| 3 | National Digital Library of India Office, Indian Institute of Technology Kharagpur | The administrative and infrastructural headquarters of the project | Dr. B. Sutradhar bsutra@ndl.gov.in |
| 4 | Project PI / Joint PI | Principal Investigator and Joint Principal Investigators of the project |
Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon |
| 5 | Website/Portal (Helpdesk) | Queries regarding NDLI and its services | support@ndl.gov.in |
| 6 | Contents and Copyright Issues | Queries related to content curation and copyright issues | content@ndl.gov.in |
| 7 | National Digital Library of India Club (NDLI Club) | Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach | clubsupport@ndl.gov.in |
| 8 | Digital Preservation Centre (DPC) | Assistance with digitizing and archiving copyright-free printed books | dpc@ndl.gov.in |
| 9 | IDR Setup or Support | Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops | idr@ndl.gov.in |
|
Loading...
|