NDLI: Can finite samples detect singularities of real-valued functions?

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

Biased random walks

Approximations of general independent distributions

Sample spaces uniform on neighborhoods

Balanced matroids

Competitive algorithms for distributed data management (extended abstract)

New algorithms for an ancient scheduling problem

Alphabet independent two dimensional matching

A constant-time optimal parallel string-matching algorithm

Methods for message routing in parallel machines

Computing Frobenius maps and factoring polynomials

Parallel computation over hyperbolic groups

Structure forest and composition factors for small base groups in nearly linear time

Feasibility testing for systems of real quadratic equations

Fault tolerant planar communication networks

Existence and construction of edge disjoint paths on expander graphs

Simple algorithms for routing on butterfly networks with bounded queues

Computing with faulty arrays

Linear decision trees: volume estimates and topological bounds

Entropy and sorting

Randomized versus nondeterministic communication complexity

Exponential lower bounds for the pigeonhole principle

Finding approximate separators and computing tree width quickly

Faster algorithms for finding small edge cuts in planar graphs

The complexity of multiway cuts (extended abstract)

Graph decomposition is NPC - a complete proof of Holyer's conjecture

Online minimization of transition systems (extended abstract)

Exponential determinization for Ω-automata with strong-fairness acceptance condition (extended abstract)

A new recursion-theoretic characterization of the polytime functions (extended abstract)

Asymptomatic conditional probabilities for first-order logic

Efficient program transformations for resilient parallel computation via randomization (preliminary version)

Efficient PRAM simulation on a distributed memory machine

A deterministic poly(log log N)-time N-processor algorithm for linear programming in fixed dimension

On the parallel complexity of computing a maximal independent set in a hypergraph

Computational learning theory: survey and selected bibliography

Learning arithmetic read-once formulas

Fast learning of k-term DNF formulas with queries

Can finite samples detect singularities of real-valued functions?

A logspace algorithm for tree canonization (extended abstract)

A hypercubic sorting network with nearly logarithmic depth

Small-depth counting networks

Shallow multiplication circuits and wise financial investments

Symmetry and complexity

When do extra majority gates help?

Representing Boolean functions as polynomials modulo composite numbers

On the degree of Boolean functions as real polynomials

On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)

A subexponential randomized simplex algorithm (extended abstract)

Polynomial algorithms for linear programming over the algebraic numbers

Fully dynamic planarity testing (extended abstract)

Planar separators and parallel polygon triangulation (preliminary version)

Ray shooting and parametric search

On the angular resolution of planar graphs

Ham-sandwich cuts in $R^{d}$

A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version)

Adapting to asynchronous dynamic networks (extended abstract)

Competitive distributed job scheduling (extended abstract)

Improved distributed algorithms for coloring and network decomposition problems

Efficient fault tolerant algorithms for resource allocation in distributed systems

The history and status of the P versus NP question

On the complexity of RAM with various operation sets

Average case intractability of matrix and diophantine problems (extended abstract)

On the hardness of computing the permanent of random matrices (extended abstract)

Simple and efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible!

Self-stabilizing symmetry breaking in constant-space (extended abstract)

A correctness condition for high-performance multiprocessors (extended abstract)

Target shooting with programmed random variables

Communication complexity of secure computation (extended abstract)

Making zero-knowledge provers efficient

A note on efficient zero-knowledge proofs and arguments (extended abstract)

Two-prover one-round proof systems: their power and their problems (extended abstract)

On the all-pairs-shortest-path problem

A parallel randomized approximation scheme for shortest paths

Biconnectivity approximations and graph carvings

e-approximations with minimum packing constraint violation (extended abstract)

Can finite samples detect singularities of real-valued functions?

Content Provider	ACM Digital Library
Author	Ben-David, Shai
Abstract	Consider the following type of problem: There is an unknown function, f : Rn → Rm, there is also a black-box that on query x (ε Rn) returns f(x). Is there an algorithm that, using probes to the black-box, can figure out analytic information about f? (For an example: “Is f a polynomial?”, “Is f a second order differentiable at x = (0,0,…,0)?” etc.).Clearly, for examples as these, if we bound the number of probes an algorithm has to settle for, no algorithm can carry the task. On the other hand, if one allows an infinite iteration of a “probe compute and guess” process, then, (quite surprisingly) for many such questions, there are algorithms that are guaranteed to be correct in all but finitely many of their guesses. We call such questions Decidable In the Limit, (DIL).We analyze the class of DIL problems and provide a necessary and sufficient condition for the membership of a decision problem in this class. We offer an algorithm for any DIL problem, and apply it to several types of learning tasks.Furthermore, if an a-priori probability distribution P, according to which f is being chosen, is available to the algorithm, then it can be strengthened into a finite algorithm. More precisely, for many distributions P, there exists a polynomial function, l, such that for every 0<δ<1, there is an algorithm using at most l(log(δ)) many probes that succeeds on more than (1–δ) of the f's (as measured by P).We believe that the new approach presented here will be found useful for many further applications.
Starting Page	390
Ending Page	399
Page Count	10
File Format	PDF
ISBN	0897915119
DOI	10.1145/129712.129749
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1992-07-01
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