On the public citation graph

Property Testing: A Learning Theory Perspective

https://doi.org/10.1561/2200000004

0 signed · 251 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/9781119243830.ch12openalex-snapshot

Testing Statistical Hypotheses

inferredcites →https://doi.org/10.1002/rsa.10013openalex-snapshot

Testing the diameter of graphs

inferredcites →https://doi.org/10.1002/rsa.10013.absopenalex-snapshot

Testing the diameter of graphs

inferredcites →https://doi.org/10.1002/rsa.10023openalex-snapshot

Testing properties of directed graphs: acyclicity and connectivity

inferredcites →https://doi.org/10.1002/rsa.10056openalex-snapshot

Testing subgraphs in large graphs

inferredcites →https://doi.org/10.1002/rsa.10078openalex-snapshot

Three theorems regarding testing graph properties

inferredcites →https://doi.org/10.1002/rsa.10110openalex-snapshot

Functions that have read‐twice constant width branching programs are not necessarily testable

inferredcites →https://doi.org/10.1002/rsa.20037openalex-snapshot

Testing graphs for colorability properties*

inferredcites →https://doi.org/10.1002/rsa.20167openalex-snapshot

Estimating the distance to a monotone function

inferredcites →https://doi.org/10.1006/jagm.1994.1005openalex-snapshot

The Algorithmic Aspects of the Regularity Lemma

inferredcites →https://doi.org/10.1006/jcss.1995.1004openalex-snapshot

Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes

inferredcites →https://doi.org/10.1006/jcss.1996.0017openalex-snapshot

Learning Sparse Multivariate Polynomials over a Field with Queries and Counterexamples

inferredcites →https://doi.org/10.1006/jcss.1997.1533openalex-snapshot

An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution

inferredcites →https://doi.org/10.1006/jcss.1999.1656openalex-snapshot

Testing Problems with Sublearning Sample Complexity

inferredcites →https://doi.org/10.1006/jcss.1999.1692openalex-snapshot

Spot-Checkers

inferredcites →https://doi.org/10.1007/11537311_23openalex-snapshot

Property Testing and the Branching Program Size of Boolean Functions

inferredcites →https://doi.org/10.1007/11538462_26openalex-snapshot

Tolerant Locally Testable Codes

inferredcites →https://doi.org/10.1007/11538462_28openalex-snapshot

A Lower Bound for Distribution-Free Monotonicity Testing

inferredcites →https://doi.org/10.1007/11776420_16openalex-snapshot

On Optimal Learning Algorithms for Multiplicity Automata

inferredcites →https://doi.org/10.1007/11830924_43openalex-snapshot

Distance Approximation in Bounded-Degree and General Sparse Graphs

inferredcites →https://doi.org/10.1007/3-540-09519-5_73openalex-snapshot

Probabilistic algorithms for sparse polynomials

inferredcites →https://doi.org/10.1007/3-540-45465-9_87openalex-snapshot

Efficient Testing of Hypergraphs

inferredcites →https://doi.org/10.1007/3-540-46769-6_26openalex-snapshot

Finding Relevant Variables in PAC Model with Membership Queries

inferredcites →https://doi.org/10.1007/3-540-48224-5_16openalex-snapshot

Approximating the Minimum Spanning Tree Weight in Sublinear Time

inferredcites →https://doi.org/10.1007/3-540-62685-9_15openalex-snapshot

Optimal attribute-efficient learning of disjunction, parity, and threshold functions

inferredcites →https://doi.org/10.1007/978-1-4612-0865-5_26openalex-snapshot

Probability Inequalities for sums of Bounded Random Variables

inferredcites →https://doi.org/10.1007/978-1-4613-9578-2_1openalex-snapshot

Introduction to Statistical Inference

inferredcites →https://doi.org/10.1007/978-3-540-27821-4_35openalex-snapshot

Distribution-Free Connectivity Testing

inferredcites →https://doi.org/10.1007/978-3-540-27836-8_35openalex-snapshot

Sublinear-Time Approximation for Clustering Via Random Sampling

inferredcites →https://doi.org/10.1007/978-3-540-31856-9_36openalex-snapshot

Information Theory in Property Testing and Monotonicity Testing in Higher Dimension

inferredcites →https://doi.org/10.1007/978-3-540-48413-4_10openalex-snapshot

Improved Testing Algorithms for Monotonicity

inferredcites →https://doi.org/10.1007/978-3-540-70575-8_41openalex-snapshot

Efficiently Testing Sparse GF(2) Polynomials

inferredcites →https://doi.org/10.1007/978-3-540-74208-1_36openalex-snapshot

Distribution-Free Testing Lower Bounds for Basic Boolean Functions

inferredcites →https://doi.org/10.1007/978-3-540-74208-1_38openalex-snapshot

On the Benefits of Adaptivity in Property Testing of Dense Graphs

inferredcites →https://doi.org/10.1007/978-3-540-85363-3_39openalex-snapshot

Breaking the ε-Soundness Bound of the Linearity Test over GF(2)

inferredcites →https://doi.org/10.1007/978-3-642-16367-8_17openalex-snapshot

Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability

inferredcites →https://doi.org/10.1007/978-3-642-22670-0_9openalex-snapshot

On Testing Expansion in Bounded-Degree Graphs

inferredcites →https://doi.org/10.1007/bf00116828openalex-snapshot

Queries and Concept Learning

inferredcites →https://doi.org/10.1007/bf01200056openalex-snapshot

Non-deterministic exponential time has two-prover interactive protocols

inferredcites →https://doi.org/10.1007/bf01200430openalex-snapshot

Non-deterministic exponential time has two-prover interactive protocols

inferredcites →https://doi.org/10.1007/s00453-001-0078-7openalex-snapshot

Property Testing in Bounded Degree Graphs

inferredcites →https://doi.org/10.1007/s004930050060openalex-snapshot

A Sublinear Bipartiteness Tester for Bounded Degree Graphs

inferredcites →https://doi.org/10.1007/s004930070001openalex-snapshot

Efficient Testing of Large Graphs

inferredcites →https://doi.org/10.1007/s004930070011openalex-snapshot

Testing Monotonicity

inferredcites →https://doi.org/10.1016/0020-0190(87)90114-1openalex-snapshot

Occam's Razor

inferredcites →https://doi.org/10.1016/0022-0000(84)90070-9openalex-snapshot

Probabilistic encryption

inferredcites →https://doi.org/10.1016/0022-0000(93)90044-wopenalex-snapshot

Self-testing/correcting with applications to numerical problems

inferredcites →https://doi.org/10.1016/0304-3975(91)90157-wopenalex-snapshot

On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields

inferredcites →https://doi.org/10.1016/j.ic.2003.09.003openalex-snapshot

On the strength of comparisons in property testing

inferredcites →https://doi.org/10.1016/j.ic.2004.10.001openalex-snapshot

Fast approximate PCPs for multidimensional bin-packing problems

inferredcites →https://doi.org/10.1016/j.ipl.2004.01.023openalex-snapshot

A lower bound for testing juntas

inferredcites →https://doi.org/10.1016/j.jcss.2003.11.004openalex-snapshot

Testing juntas

inferredcites →https://doi.org/10.1016/j.jcss.2004.04.002openalex-snapshot

Learning functions of k relevant variables

inferredcites →https://doi.org/10.1016/j.jcss.2004.04.008openalex-snapshot

Testing subgraphs in directed graphs

inferredcites →https://doi.org/10.1016/j.jcss.2006.03.002openalex-snapshot

Tolerant property testing and distance approximation

inferredcites →https://doi.org/10.1016/j.tcs.2004.09.031openalex-snapshot

Testing hypergraph colorability

inferredcites →https://doi.org/10.1016/s0020-0190(03)00230-8openalex-snapshot

Functions that have read-once branching programs of quadratic size are not necessarily testable

inferredcites →https://doi.org/10.1016/s0020-0190(97)00021-5openalex-snapshot

On learning multivariate polynomials under the uniform distribution

inferredcites →https://doi.org/10.1016/s0196-6774(03)00019-1openalex-snapshot

Testing satisfiability

inferredcites →https://doi.org/10.1016/s0747-7171(08)80018-1openalex-snapshot

Interpolating polynomials from their values

inferredcites →https://doi.org/10.1017/s0963548306007759openalex-snapshot

A Characterization of Easily Testable Induced Subgraphs

inferredcites →https://doi.org/10.1023/a:1022615600103openalex-snapshot

Toward Efficient Agnostic Learning

inferredcites →https://doi.org/10.1023/a:1022627018023openalex-snapshot

Active Learning Using Arbitrary Binary Valued Queries

inferredcites →https://doi.org/10.1023/a:1022869011914openalex-snapshot

Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

inferredcites →https://doi.org/10.1023/a:1022870506888openalex-snapshot

Probably Almost Discriminative Learning

inferredcites →https://doi.org/10.1080/01621459.1963.10500830openalex-snapshot

Probability Inequalities for Sums of Bounded Random Variables

inferredcites →https://doi.org/10.1109/18.556674openalex-snapshot

Linearity testing in characteristic two

inferredcites →https://doi.org/10.1109/ccc.2004.18openalex-snapshot

Lower bounds for testing bipartiteness in dense graphs

inferredcites →https://doi.org/10.1109/focs.2004.64openalex-snapshot

Testing Low-Degree Polynomials over Prime Fields

inferredcites →https://doi.org/10.1109/focs.2007.11openalex-snapshot

Non-Preemptive Min-Sum Scheduling with Resource Augmentation

inferredcites →https://doi.org/10.1109/focs.2007.67openalex-snapshot

Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting

inferredcites →https://doi.org/10.1109/focs.2007.69openalex-snapshot

Balloon Popping With Applications to Ascending Auctions

inferredcites →https://doi.org/10.1109/istcs.1995.377032openalex-snapshot

Some improvements to total degree tests

inferredcites →https://doi.org/10.1109/sfcs.1991.185341openalex-snapshot

Approximating clique is almost NP-complete

inferredcites →https://doi.org/10.1109/sfcs.1998.743491openalex-snapshot

On learning monotone Boolean functions

inferredcites →https://doi.org/10.1109/sfcs.2000.892113openalex-snapshot

Testing that distributions are close

inferredcites →https://doi.org/10.1109/sfcs.2001.959920openalex-snapshot

Testing random variables for independence and identity

inferredcites →https://doi.org/10.1109/sfcs.2002.1181886openalex-snapshot

A lower bound for testing 3-colorability in bounded-degree graphs

inferredcites →https://doi.org/10.1109/sfcs.2005.5openalex-snapshot

A Characterization of the (natural) Graph Properties Testable with One-Sided Error

inferredcites →https://doi.org/10.1109/sffcs.1999.814587openalex-snapshot

A sublinear time approximation scheme for clustering in metric spaces

inferredcites →https://doi.org/10.1109/sffcs.1999.814638openalex-snapshot

Boosting and hard-core sets

inferredcites →https://doi.org/10.1109/tit.2005.856958openalex-snapshot

Testing Reed–Muller Codes

inferredcites →https://doi.org/10.1137/0219073openalex-snapshot

Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields

inferredcites →https://doi.org/10.1137/0220019openalex-snapshot

Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$

inferredcites →https://doi.org/10.1137/0221014openalex-snapshot

On Learning Ring-Sum-Expansions

inferredcites →https://doi.org/10.1137/050627915openalex-snapshot

Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs

inferredcites →https://doi.org/10.1137/050645804openalex-snapshot

Distribution-Free Property-Testing

inferredcites →https://doi.org/10.1137/060652324openalex-snapshot

Testing versus Estimation of Graph Properties

inferredcites →https://doi.org/10.1137/080734066openalex-snapshot

Testing Symmetric Properties of Distributions

inferredcites →https://doi.org/10.1137/s0097539700366528openalex-snapshot

Regular Languages are Testable with a Constant Number of Queries

inferredcites →https://doi.org/10.1137/s009753970038211xopenalex-snapshot

Testing Membership in Languages that Have Small Width Branching Programs

inferredcites →https://doi.org/10.1137/s0097539702403645openalex-snapshot

The Complexity of Approximating the Entropy

inferredcites →https://doi.org/10.1137/s0097539702414026openalex-snapshot

On Testing Convexity and Submodularity

inferredcites →https://doi.org/10.1137/s0097539703436424openalex-snapshot

Tight Bounds for Testing Bipartiteness in General Graphs

inferredcites →https://doi.org/10.1137/s009753970444199xopenalex-snapshot

Abstract Combinatorial Programs and Efficient Property Testers

inferredcites →https://doi.org/10.1137/s0097539704445445openalex-snapshot

Some 3CNF Properties Are Hard to Test

inferredcites →https://doi.org/10.1137/s0097539704445615openalex-snapshot

Testing Polynomials over General Fields

inferredcites →https://doi.org/10.1137/s009753970445603openalex-snapshot

The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance

inferredcites →https://doi.org/10.1137/s0097539792239291openalex-snapshot

Randomized Interpolation and Approximation of Sparse Polynomials

inferredcites →https://doi.org/10.1137/s0097539793255151openalex-snapshot

Robust Characterizations of Polynomials with Applications to Program Testing

inferredcites →https://doi.org/10.1137/s009753979732058xopenalex-snapshot

Simple Learning Algorithms for Decision Trees and Multivariate Polynomials

inferredcites →https://doi.org/10.1137/s0895480101407444openalex-snapshot

Testing Basic Boolean Formulae

inferredcites →https://doi.org/10.1137/s0895480102410973openalex-snapshot

Testing of Clustering

inferredcites →https://doi.org/10.1137/s0895480199358655openalex-snapshot

Testing k -colorability

inferredcites →https://doi.org/10.1145/1007352.1007414openalex-snapshot

Sublinear algorithms for testing monotone and unimodal distributions

inferredcites →https://doi.org/10.1145/1007352.1007421openalex-snapshot

Derandomizing homomorphism testing in general groups

inferredcites →https://doi.org/10.1145/103418.103428openalex-snapshot

Checking computations in polylogarithmic time

inferredcites →https://doi.org/10.1145/103418.103429openalex-snapshot

Self-testing/correcting for polynomials and for approximate functions

inferredcites →https://doi.org/10.1145/1060590.1060611openalex-snapshot

Every monotone graph property is testable

inferredcites →https://doi.org/10.1145/1109557.1109589openalex-snapshot

Testing triangle-freeness in general graphs

inferredcites →https://doi.org/10.1145/1132516.1132555openalex-snapshot

A combinatorial characterization of the testable graph properties

inferredcites →https://doi.org/10.1145/1132516.1132556openalex-snapshot

Graph limits and parameter testing

inferredcites →https://doi.org/10.1145/1250790.1250863openalex-snapshot

Testing k-wise and almost k-wise independence

inferredcites →https://doi.org/10.1145/129712.129749openalex-snapshot

Can finite samples detect singularities of real-valued functions?

inferredcites →https://doi.org/10.1145/168304.168307openalex-snapshot

Learning sparse multivariate polynomials over a field with queries and counterexamples

inferredcites →https://doi.org/10.1145/168304.168318openalex-snapshot

On probably correct classification of concepts

inferredcites →https://doi.org/10.1145/174644.174647openalex-snapshot

Cryptographic Limitations on Learning Boolean Formulae and Finite Automata

inferredcites →https://doi.org/10.1145/195613.195656openalex-snapshot

Learning Boolean formulas

inferredcites →https://doi.org/10.1145/1968.1972openalex-snapshot

A theory of the learnable

inferredcites →https://doi.org/10.1145/226643.226652openalex-snapshot

Interactive proofs and the hardness of approximating cliques

inferredcites →https://doi.org/10.1145/258533.258642openalex-snapshot

Improved low-degree testing and its applications

inferredcites →https://doi.org/10.1145/273865.273901openalex-snapshot

Probabilistic checking of proofs

inferredcites →https://doi.org/10.1145/285055.285060openalex-snapshot

Property testing and its connection to learning and approximation

inferredcites →https://doi.org/10.1145/307400.307472openalex-snapshot

More efficient PAC-learning of DNF with membership queries under the uniform distribution

inferredcites →https://doi.org/10.1145/337244.337257openalex-snapshot

Learning functions represented as multiplicity automata

inferredcites →https://doi.org/10.1145/3749740.3749746openalex-snapshot

A Theory of the Learnable

inferredcites →https://doi.org/10.1145/509907.509977openalex-snapshot

Monotonicity testing over general poset domains

inferredcites →https://doi.org/10.1145/62212.62241openalex-snapshot

A deterministic algorithm for sparse multivariate polynomial interpolation

inferredcites →https://doi.org/10.1145/780542.780590openalex-snapshot

A sublinear algorithm for weakly approximating edit distance

inferredcites →https://doi.org/10.1214/aoms/1177729330openalex-snapshot

A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

inferredcites →https://doi.org/10.4086/toc.2005.v001a009openalex-snapshot

inferredcites →https://doi.org/10.4086/toc.2006.v002a009openalex-snapshot

inferredcites →https://doi.org/10.5555/1109557.1109589openalex-snapshot

Testing triangle-freeness in general graphs

inferredcites →https://doi.org/10.5555/365411.365499openalex-snapshot

Sublinear time approximate clustering

inferredcites →https://doi.org/10.5555/92571.92620openalex-snapshot

Learning functions of k terms

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.2139/ssrn.4805894openalex-extracted

Almost Optimal Adaptive Proper Learning Polynomials

inferred← citeshttps://doi.org/10.1002/rsa.20462openalex-snapshot

Finding cycles and trees in sublinear time

inferred← citeshttps://doi.org/10.1002/rsa.20507openalex-snapshot

A unified framework for testing linear‐invariant properties

inferred← citeshttps://doi.org/10.1002/rsa.20582openalex-snapshot

Two-sided error proximity oblivious testing

inferred← citeshttps://doi.org/10.1007/978-1-4614-6642-0_4openalex-snapshot

Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition

inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_701openalex-snapshot

Testing Bipartiteness of Graphs in Sublinear Time

inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_702openalex-snapshot

Testing Bipartiteness in the Dense-Graph Model

inferred← citeshttps://doi.org/10.1007/978-3-030-43662-9_7openalex-snapshot

On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing

inferred← citeshttps://doi.org/10.1007/978-3-030-96731-4_17openalex-snapshot

An Optimal Tester for k-Linear

inferred← citeshttps://doi.org/10.1007/978-3-031-20624-5_19openalex-snapshot

Almost Optimal Proper Learning and Testing Polynomials

inferred← citeshttps://doi.org/10.1007/978-3-031-30448-4_12openalex-snapshot

On One-Sided Testing Affine Subspaces

inferred← citeshttps://doi.org/10.1007/978-3-319-15579-1_58openalex-snapshot

Sublinear DTD Validity

inferred← citeshttps://doi.org/10.1007/978-3-540-70529-1_212openalex-snapshot

Property Testing

inferred← citeshttps://doi.org/10.1007/978-3-642-03685-9_38openalex-snapshot

Hierarchy Theorems for Property Testing

inferred← citeshttps://doi.org/10.1007/978-3-642-03685-9_39openalex-snapshot

Algorithmic Aspects of Property Testing in the Dense Graphs Model

inferred← citeshttps://doi.org/10.1007/978-3-642-03685-9_51openalex-snapshot

Testing Computability by Width Two OBDDs

inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_30openalex-snapshot

Testing Boolean Function Isomorphism

inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_43openalex-snapshot

On Testing Computability by Small Width OBDDs

inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_1openalex-snapshot

A Brief Introduction to Property Testing

inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_22openalex-snapshot

Hierarchy Theorems for Property Testing

inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_23openalex-snapshot

Algorithmic Aspects of Property Testing in the Dense Graphs Model

inferred← citeshttps://doi.org/10.1007/978-3-642-20920-8_19openalex-snapshot

Untestable Properties in the Kahr-Moore-Wang Class

inferred← citeshttps://doi.org/10.1007/978-3-642-22670-0_19openalex-snapshot

Proximity Oblivious Testing and the Role of Invariances

inferred← citeshttps://doi.org/10.1007/978-3-642-22670-0_31openalex-snapshot

A Brief Introduction to Property Testing

inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_49openalex-snapshot

Proximity Oblivious Testing and the Role of Invariances

inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_701-1openalex-snapshot

Testing Bipartiteness of Graphs in Sublinear Time

inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_702-1openalex-snapshot

Testing Bipartiteness in the Dense-Graph Model

inferred← citeshttps://doi.org/10.1007/978-3-642-31155-0_33openalex-snapshot

Testing Formula Satisfaction

inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_37openalex-snapshot

Tight Bounds for Testing k-Linearity

inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_48openalex-snapshot

Two-Sided Error Proximity Oblivious Testing

inferred← citeshttps://doi.org/10.1007/978-3-642-40328-6_38openalex-snapshot

Testing Membership in Counter Automaton Languages

inferred← citeshttps://doi.org/10.1007/978-3-642-54423-1_27openalex-snapshot

Helly-Type Theorems in Property Testing

inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_24openalex-snapshot

Big Data on the Rise?

inferred← citeshttps://doi.org/10.1007/978-3-662-53426-7_4openalex-snapshot

Fast Distributed Algorithms for Testing Graph Properties

inferred← citeshttps://doi.org/10.1007/s00037-011-0022-4openalex-snapshot

Hierarchy Theorems for Property Testing

inferred← citeshttps://doi.org/10.1007/s00037-012-0040-xopenalex-snapshot

Property Testing Lower Bounds via Communication Complexity

inferred← citeshttps://doi.org/10.1007/s00037-018-0168-4openalex-snapshot

An adaptivity hierarchy theorem for property testing

inferred← citeshttps://doi.org/10.1007/s00037-021-00212-3openalex-snapshot

An Exponential Separation Between MA and AM Proofs of Proximity

inferred← citeshttps://doi.org/10.1007/s00220-023-04836-0openalex-snapshot

Discrimination of Quantum States Under Locality Constraints in the Many-Copy Setting

inferred← citeshttps://doi.org/10.1007/s00224-017-9785-6openalex-snapshot

Testing Shape Restrictions of Discrete Distributions

inferred← citeshttps://doi.org/10.1007/s00446-018-0324-8openalex-snapshot

Fast distributed algorithms for testing graph properties

inferred← citeshttps://doi.org/10.1007/s00453-013-9858-0openalex-snapshot

Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities

inferred← citeshttps://doi.org/10.1007/s11856-021-2228-8openalex-snapshot

Testing graphs against an unknown distribution

inferred← citeshttps://doi.org/10.1016/j.ipl.2010.07.012openalex-snapshot

A local decision test for sparse polynomials

inferred← citeshttps://doi.org/10.1016/j.jcss.2012.01.007openalex-snapshot

Testable and untestable classes of first-order formulae

inferred← citeshttps://doi.org/10.1016/j.tcs.2010.10.003openalex-snapshot

Sorting and selection on dynamic data

inferred← citeshttps://doi.org/10.1016/j.tcs.2011.06.038openalex-snapshot

Testing Eulerianity and connectivity in directed sparse graphs

inferred← citeshttps://doi.org/10.1016/j.tcs.2011.12.003openalex-snapshot

Some results on approximate 1-median selection in metric spaces

inferred← citeshttps://doi.org/10.1016/j.tcs.2013.03.004openalex-snapshot

Approximate membership for regular languages modulo the edit distance

inferred← citeshttps://doi.org/10.1016/j.tcs.2015.08.014openalex-snapshot

Boosting distinct random sampling for basic counting on the union of distributed streams

inferred← citeshttps://doi.org/10.1016/j.tcs.2018.05.019openalex-snapshot

Testing piecewise functions

inferred← citeshttps://doi.org/10.1016/j.tcs.2024.114745openalex-snapshot

On one-sided testing affine subspaces

inferred← citeshttps://doi.org/10.1017/9781108135252openalex-snapshot

Introduction to Property Testing

inferred← citeshttps://doi.org/10.1017/s0963548315000292openalex-snapshot

On Active and Passive Testing

inferred← citeshttps://doi.org/10.1038/s41534-020-00288-9openalex-snapshot

The Born supremacy: quantum advantage and training of an Ising Born machine

inferred← citeshttps://doi.org/10.1109/ccc.2011.31openalex-snapshot

Property Testing Lower Bounds via Communication Complexity

inferred← citeshttps://doi.org/10.1109/focs.2010.53openalex-snapshot

A Unified Framework for Testing Linear-Invariant Properties

inferred← citeshttps://doi.org/10.1109/focs.2012.64openalex-snapshot

Active Property Testing

inferred← citeshttps://doi.org/10.1109/focs.2017.86openalex-snapshot

Generalized Uniformity Testing

inferred← citeshttps://doi.org/10.1109/icces67310.2025.11337167openalex-snapshot

AI Powered Server Log Management Software

inferred← citeshttps://doi.org/10.1109/tit.2025.3646804openalex-snapshot

The Minimax Risk in Testing Uniformity Over Large Alphabets Under Missing-Ball Alternatives

inferred← citeshttps://doi.org/10.1137/090749621openalex-snapshot

Algorithmic Aspects of Property Testing in the Dense Graphs Model

inferred← citeshttps://doi.org/10.1137/1.9781611973730.122openalex-snapshot

Testing Poisson Binomial Distributions

inferred← citeshttps://doi.org/10.1137/1.9781611976014.10openalex-snapshot

Fast Fourier Sparsity Testing

inferred← citeshttps://doi.org/10.1137/100789646openalex-snapshot

On Proximity-Oblivious Testing

inferred← citeshttps://doi.org/10.1137/100791075openalex-snapshot

Sublinear Time Algorithms

inferred← citeshttps://doi.org/10.1137/110832677openalex-snapshot

Nearly Tight Bounds for Testing Function Isomorphism

inferred← citeshttps://doi.org/10.1137/130945508openalex-snapshot

Testing Probability Distributions using Conditional Samples

inferred← citeshttps://doi.org/10.1142/s0129054112500219openalex-snapshot

TESTING FOR FORBIDDEN POSETS IN ORDERED ROOTED FORESTS

inferred← citeshttps://doi.org/10.1142/s0218195918500115openalex-snapshot

Helly-Type Theorems in Property Testing

inferred← citeshttps://doi.org/10.1145/2090236.2090249openalex-snapshot

Algorithms on evolving graphs

inferred← citeshttps://doi.org/10.1145/2213556.2213561openalex-snapshot

Approximating and testing k-histogram distributions in sub-linear time

inferred← citeshttps://doi.org/10.1145/2339530.2339539openalex-snapshot

PageRank on an evolving graph

inferred← citeshttps://doi.org/10.1145/2554797.2554841openalex-snapshot

Partial tests, universal tests and decomposability

inferred← citeshttps://doi.org/10.1145/2618243.2618256openalex-snapshot

Boosting the basic counting on distributed streams

inferred← citeshttps://doi.org/10.1145/2688073.2688079openalex-snapshot

Non-Interactive Proofs of Proximity

inferred← citeshttps://doi.org/10.1145/2688073.2688080openalex-snapshot

On Sample-Based Testers

inferred← citeshttps://doi.org/10.1145/2897184openalex-snapshot

Testing Read-Once Formula Satisfaction

inferred← citeshttps://doi.org/10.1145/2898355openalex-snapshot

On Sample-Based Testers

inferred← citeshttps://doi.org/10.1145/2902251.2902274openalex-snapshot

Are Few Bins Enough

inferred← citeshttps://doi.org/10.1145/3055399.3055461openalex-snapshot

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

inferred← citeshttps://doi.org/10.1145/3188745.3188842openalex-snapshot

Distribution-free junta testing

inferred← citeshttps://doi.org/10.1145/3213772openalex-snapshot

Settling the Query Complexity of Non-adaptive Junta Testing

inferred← citeshttps://doi.org/10.1145/3264434openalex-snapshot

Distribution-free Junta Testing

inferred← citeshttps://doi.org/10.1145/3357713.3384239openalex-snapshot

Testing noisy linear functions for sparsity

inferred← citeshttps://doi.org/10.1145/3580374openalex-snapshot

A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts

inferred← citeshttps://doi.org/10.1145/3717823.3718166openalex-snapshot

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model

inferred← citeshttps://doi.org/10.1145/3717823.3718228openalex-snapshot

Improved Bounds for Testing Low Stabilizer Complexity States

inferred← citeshttps://doi.org/10.1184/r1/6720509openalex-snapshot

Mathematical Theories of Interaction with Oracles

inferred← citeshttps://doi.org/10.1201/b19567-14openalex-snapshot

High-Dimensional Computational Geometry

inferred← citeshttps://doi.org/10.1214/18-aos1729openalex-snapshot

Hypothesis testing for densities and high-dimensional multinomials: Sharp local minimax rates

inferred← citeshttps://doi.org/10.31237/osf.io/rx6zt_v1openalex-snapshot

Property Testing and Probability Distributions: New Techniques, New Models, and New Goals

inferred← citeshttps://doi.org/10.4086/toc.2014.v010a020openalex-snapshot

inferred← citeshttps://doi.org/10.4086/toc.2018.v014a019openalex-snapshot

inferred← citeshttps://doi.org/10.4086/toc.gs.2016.007openalex-snapshot

inferred← citeshttps://doi.org/10.4086/toc.gs.2020.009openalex-snapshot

inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2014.704openalex-snapshot

On Multiple Input Problems in Property Testing

inferred← citeshttps://doi.org/10.4230/lipics.approx/random.2020.5openalex-snapshot

Almost Optimal Testers for Concise Representations

inferred← citeshttps://doi.org/10.4230/lipics.ccc.2019.2openalex-snapshot

Almost Optimal Distribution-Free Junta Testing

inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2010.145openalex-snapshot

New Results on Quantum Property Testing

inferred← citeshttps://doi.org/10.4230/lipics.itcs.2019.52openalex-snapshot

Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

inferred← citeshttps://doi.org/10.48550/arxiv.1005.0523openalex-snapshot

New Results on Quantum Property Testing

inferred← citeshttps://doi.org/10.48550/arxiv.1008.4401openalex-snapshot

Separations of Matroid Freeness Properties

inferred← citeshttps://doi.org/10.48550/arxiv.1107.2700openalex-snapshot

Learning $k$-Modal Distributions via Testing

inferred← citeshttps://doi.org/10.48550/arxiv.1111.0897openalex-snapshot

Active Property Testing

inferred← citeshttps://doi.org/10.48550/arxiv.1204.3413openalex-snapshot

Testing Formula Satisfaction

inferred← citeshttps://doi.org/10.48550/arxiv.1205.4349openalex-snapshot

From Exact Learning to Computing Boolean Functions and Back Again

inferred← citeshttps://doi.org/10.48550/arxiv.1306.1360openalex-snapshot

Some properties are not even partially testable

inferred← citeshttps://doi.org/10.48550/arxiv.1310.2035openalex-snapshot

A Survey of Quantum Property Testing

inferred← citeshttps://doi.org/10.48550/arxiv.1411.7346openalex-snapshot

A Chasm Between Identity and Equivalence Testing with Conditional Queries

inferred← citeshttps://doi.org/10.48550/arxiv.1501.06783openalex-snapshot

Big Data on the Rise: Testing monotonicity of distributions

inferred← citeshttps://doi.org/10.48550/arxiv.1602.03718openalex-snapshot

Fast Distributed Algorithms for Testing Graph Properties

inferred← citeshttps://doi.org/10.48550/arxiv.1704.06314openalex-snapshot

Settling the query complexity of non-adaptive junta testing

inferred← citeshttps://doi.org/10.48550/arxiv.1802.04859openalex-snapshot

Distribution-free Junta Testing

inferred← citeshttps://doi.org/10.5555/2133036.2133166openalex-snapshot

Nearly tight bounds for testing function isomorphism

inferred← citeshttps://doi.org/10.5555/2627817.2627913openalex-snapshot

Exponentially improved algorithms and lower bounds for testing signed majorities

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.