NDLI: Restriction access

Please wait, while we are loading the content...

High-confidence predictions under adversarial uncertainty

Learning hurdles for sleeping experts

Restriction access

Mechanism design with approximate valuations

Quantum strategic game theory

The curse of simultaneity

No justified complaints: on fair sharing of multiple resources

From randomizing polynomials to parallel algorithms

Practical verified computation with streaming interactive proofs

Paging for multi-core shared caches

Noise vs computational intractability in dynamics

Distribution free evolvability of polynomial functions over all convex loss functions

Algorithms on evolving graphs

Towards deterministic tree code constructions

Linear time decoding of regular expander codes

List decoding subspace codes from insertions and deletions

Bounds on locally testable codes with unique tests

Approximately optimal mechanism design via differential privacy

Fairness through awareness

Dynamics of prisoner's dilemma and the evolution of cooperation on networks

Crowdsourced Bayesian auctions

Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure

Quantum interactive proofs with weak error bounds

Quantum money from knots

Quantum rejection sampling

(Leveled) fully homomorphic encryption without bootstrapping

From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again

Targeted malleability: homomorphic encryption for restricted computations

Sherali-Adams relaxations and indistinguishability in counting logics

Graph densification

Spectral sparsification via random spanners

Multicommodity flows and cuts in polymatroidal networks

On the degree of univariate polynomials over the integers

On persistent homotopy, knotted complexes and the Alexander module

Compressed matrix multiplication

Gadgets and anti-gadgets leading to a complexity dichotomy

On beating the hybrid argument

Linear programming, width-1 CSPs, and robust satisfaction

Marginal hitting sets imply super-polynomial lower bounds for permanent

Restriction access

Content Provider	ACM Digital Library
Author	Yehudayoff, Amir Wigderson, Avi Dvir, Zeev Rao, Anup
Abstract	We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call restriction access. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On one extreme, full restrictions (assigning all variables) correspond to evaluating the device on a complete input, yielding the result of the computation on that input, which is the same as standard black-box access. On the other extreme, empty restrictions (assigning no variables) yield a full description of the original device. We explore the grey-scale of possibilities in the middle. Focusing on learning theory, we show that restriction access provides a setting in which one can obtain positive results for problems that have resisted attack in the black-box access model. We introduce a PAC-learning version of restriction access, and show that one can efficiently learn both decision trees and DNF formulas in this model. These two classes are not known to be learnable in the PAC model with black-box access. Our DNF learning algorithm is obtained by a reduction to a general learning problem we call population recovery, in which random samples from an unknown distribution become available only after a random part of each is obliterated. Specifically, assume that every member of an unknown population is described by a vector of values. The algorithm has access to random samples, each of which is a random member of the population, whose values are given only on a random subset of the attributes. Analyzing our efficient algorithm to fully recover the unknown population calls for understanding another basic problem of independent interest: "robust local inversion" of matrices. The population recovery algorithm and construction of robust local inverses for some families of matrices are the main technical contributions of the paper. We also discuss other possible variants of restriction access, in which the values to restricted variables, as well as the subset of free (unassigned) variables, are generated deterministically or randomly, in friendly or adversarial fashions. We discuss how these models may naturally suit situations in computational learning, computational biology, automated proofs, cryptography and complexity theory.
Starting Page	19
Ending Page	33
Page Count	15
File Format	PDF
ISBN	9781450311151
DOI	10.1145/2090236.2090239
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-01-08
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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