On the public citation graph

Lower Bounds for Testing Function Isomorphism

0 signed · 49 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/rsa.20300openalex-snapshot
Testability and repair of hereditary hypergraph properties
inferredcites →https://doi.org/10.1007/978-3-030-60754-8_27openalex-snapshot
Noise Stability of Weighted Majority
inferredcites →https://doi.org/10.1007/978-3-642-03685-9_48openalex-snapshot
Testing ±1-weight halfspace
inferredcites →https://doi.org/10.1016/j.fertnstert.2005.08.063openalex-snapshot
One at a time
inferredcites →https://doi.org/10.1016/j.jcss.2003.11.004openalex-snapshot
Testing juntas
inferredcites →https://doi.org/10.1109/ccc.2010.29openalex-snapshot
Fooling Functions of Halfspaces under Product Distributions
inferredcites →https://doi.org/10.1109/focs.2008.44openalex-snapshot
Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes
inferredcites →https://doi.org/10.1109/sfcs.1977.24openalex-snapshot
Probabilistic computations: Toward a unified measure of complexity
inferredcites →https://doi.org/10.1109/sfcs.1995.492573openalex-snapshot
Free bits, PCPs and non-approximability-towards tight results
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.1137/060667177openalex-snapshot
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
inferredcites →https://doi.org/10.1137/070680795openalex-snapshot
Testing Graph Isomorphism
inferredcites →https://doi.org/10.1137/1.9781611973068.29openalex-snapshot
Testing Halfspaces
inferredcites →https://doi.org/10.1137/s0040585x97982591openalex-snapshot
Sharpening of the Upper Bound of the Absolute Constant in the Berry–Esseen Inequality
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/s0097539793255151openalex-snapshot
Robust Characterizations of Polynomials with Applications to Program Testing
inferredcites →https://doi.org/10.1137/s0097539796302531openalex-snapshot
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
inferredcites →https://doi.org/10.1137/s0895480101407444openalex-snapshot
Testing Basic Boolean Formulae
inferredcites →https://doi.org/10.1145/1060590.1060611openalex-snapshot
Every monotone graph property is testable
inferredcites →https://doi.org/10.1145/1132516.1132555openalex-snapshot
A combinatorial characterization of the testable graph properties
inferredcites →https://doi.org/10.4007/annals.2010.171.295openalex-snapshot
Noise stability of functions with low influences: Invariance and optimality
inferredcites →https://doi.org/10.48550/arxiv.0801.2179openalex-snapshot
On the testability and repair of hereditary hypergraph properties
inferredcites →https://doi.org/10.48550/arxiv.math/0412377openalex-snapshot
Noise Stability of Weighted Majority

What points at this work

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

inferred← citeshttps://doi.org/10.1002/rsa.20507openalex-snapshot
A unified framework for testing linear‐invariant properties
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-28332-1_8openalex-snapshot
Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
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-40328-6_39openalex-snapshot
Tight Lower Bounds for Testing Linear Isomorphism
inferred← citeshttps://doi.org/10.1007/s00037-012-0040-xopenalex-snapshot
Property Testing Lower Bounds via Communication Complexity
inferred← citeshttps://doi.org/10.1007/s00453-013-9817-9openalex-snapshot
Local Correction with Constant Error Rate
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.1016/j.ic.2014.08.003openalex-snapshot
Isomorphism testing of Boolean functions computable by constant-depth circuits
inferred← citeshttps://doi.org/10.1016/j.ipl.2011.12.005openalex-snapshot
Local correction of juntas
inferred← citeshttps://doi.org/10.1109/ccc.2011.31openalex-snapshot
Property Testing Lower Bounds via Communication Complexity
inferred← citeshttps://doi.org/10.1109/ccc.2012.28openalex-snapshot
Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching
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.53openalex-snapshot
Partially Symmetric Functions Are Efficiently Isomorphism-Testable
inferred← citeshttps://doi.org/10.1109/focs.2014.38openalex-snapshot
New Algorithms and Lower Bounds for Monotonicity Testing
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00030openalex-snapshot
An Invariance Principle for the Multi-slice, with Applications
inferred← citeshttps://doi.org/10.1145/2395116.2395118openalex-snapshot
An invariance principle for polytopes
inferred← citeshttps://doi.org/10.1609/hcomp.v10i1.21991openalex-snapshot
Near-Optimal Reviewer Splitting in Two-Phase Paper Reviewing and Conference Experiment Design
inferred← citeshttps://doi.org/10.3233/fi-2021-2076openalex-snapshot
Testing Boolean Functions Properties
inferred← citeshttps://doi.org/10.46298/.8500openalex-snapshot
Testing Boolean Functions Properties
inferred← citeshttps://doi.org/10.48550/arxiv.1210.5677openalex-snapshot
Local Correction with Constant Error Rate
inferred← citeshttps://doi.org/10.48550/arxiv.1407.7763openalex-snapshot
Social choice, computational complexity, Gaussian geometry, and Boolean functions
inferred← citeshttps://doi.org/10.48550/arxiv.1708.05640openalex-snapshot
A similarity criterion for sequential programs using truth-preserving partial functions
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
inferred← citeshttps://doi.org/10.7916/d8251gb1openalex-snapshot
Analytic Methods in Concrete Complexity
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.