On the public citation graph
Simple analysis of graph tests for linearity and PCP
0 signed · 85 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/3-540-44666-4_27openalex-snapshot
The Non-approximability of Non-Boolean Predicates
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.1109/18.556674openalex-snapshot
Linearity testing in characteristic two
inferredcites →https://doi.org/10.1109/sfcs.1995.492573openalex-snapshot
Free bits, PCPs and non-approximability-towards tight results
inferredcites →https://doi.org/10.1137/s0097539795280895openalex-snapshot
A Parallel Repetition Theorem
inferredcites →https://doi.org/10.1137/s0097539796302531openalex-snapshot
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
inferredcites →https://doi.org/10.1145/226643.226652openalex-snapshot
Interactive proofs and the hardness of approximating cliques
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/273865.273901openalex-snapshot
Probabilistic checking of proofs
inferredcites →https://doi.org/10.1145/278298.278306openalex-snapshot
Proof verification and the hardness of approximation problems
inferredcites →https://doi.org/10.1145/285055.285059openalex-snapshot
A threshold of ln n for approximating set cover
inferredcites →https://doi.org/10.1145/335305.335329openalex-snapshot
A PCP characterization of NP with optimal amortized query complexity
inferredcites →https://doi.org/10.21136/cpmf.1938.122006openalex-snapshot
On sequences of integers containing no arithmetic progression
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/9781118600207.ch13openalex-snapshot
Inapproximability of Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1002/9781119005353.ch13openalex-snapshot
Inapproximability of Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1002/rsa.20182openalex-snapshot
Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
inferred← citeshttps://doi.org/10.1002/rsa.20226openalex-snapshot
More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
inferred← citeshttps://doi.org/10.1002/rsa.20549openalex-snapshot
A query efficient non-adaptive long code test with perfect completeness
inferred← citeshttps://doi.org/10.1007/978-0-387-30162-4_202openalex-snapshot
Linearity Testing/Testing Hadamard Codes
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_202openalex-snapshot
Linearity Testing/Testing Hadamard Codes
inferred← citeshttps://doi.org/10.1007/978-3-540-31856-9_16openalex-snapshot
More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP
inferred← citeshttps://doi.org/10.1007/978-3-540-79228-4_9openalex-snapshot
Derandomizing Graph Tests for Homomorphism
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_39openalex-snapshot
Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_7openalex-snapshot
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
inferred← citeshttps://doi.org/10.1007/978-3-642-03685-9_34openalex-snapshot
A Hypergraph Dictatorship Test with Perfect Completeness
inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_55openalex-snapshot
A Query Efficient Non-adaptive Long Code Test with Perfect Completeness
inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_20openalex-snapshot
Query-Efficient Dictatorship Testing with Perfect Completeness
inferred← citeshttps://doi.org/10.1007/978-3-642-22685-4_41openalex-snapshot
Characterizations of Locally Testable Linear- and Affine-Invariant Families
inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_22openalex-snapshot
Black-Box Reductions in Mechanism Design
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_202-2openalex-snapshot
Linearity and Group Homomorphism Testing/Testing Hadamard Codes
inferred← citeshttps://doi.org/10.1007/s00224-015-9639-zopenalex-snapshot
A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness
inferred← citeshttps://doi.org/10.1007/s00493-010-2455-9openalex-snapshot
Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs
inferred← citeshttps://doi.org/10.1007/s10474-020-01076-9openalex-snapshot
Colorings with only rainbow arithmetic progressions
inferred← citeshttps://doi.org/10.1007/s11856-021-2164-7openalex-snapshot
On non-optimally expanding sets in Grassmann graphs
inferred← citeshttps://doi.org/10.1016/j.jcss.2007.06.002openalex-snapshot
Finding large 3-free sets I: The small n case
inferred← citeshttps://doi.org/10.1016/j.tcs.2010.12.046openalex-snapshot
On the derandomization of the graph test for homomorphism over groups
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.09.030openalex-snapshot
Characterizations of locally testable linear- and affine-invariant families
inferred← citeshttps://doi.org/10.1109/focs.2008.60openalex-snapshot
Two Query PCP with Sub-Constant Error
inferred← citeshttps://doi.org/10.1109/focs.2010.71openalex-snapshot
A Fourier-Analytic Approach to Reed-Muller Decoding
inferred← citeshttps://doi.org/10.1109/focs.2012.75openalex-snapshot
Hardness of Finding Independent Sets in Almost q-Colorable Graphs
inferred← citeshttps://doi.org/10.1109/sfcs.2005.41openalex-snapshot
Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion
inferred← citeshttps://doi.org/10.1112/blms.12005openalex-snapshot
On graphs decomposable into induced matchings of linear sizes
inferred← citeshttps://doi.org/10.1137/070681612openalex-snapshot
Gowers Uniformity, Influence of Variables, and PCPs
inferred← citeshttps://doi.org/10.1137/080715548openalex-snapshot
Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)
inferred← citeshttps://doi.org/10.1137/1.9781611975482.3openalex-snapshot
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
inferred← citeshttps://doi.org/10.1137/19m1248108openalex-snapshot
Sparse Hypergraphs with Applications to Coding Theory
inferred← citeshttps://doi.org/10.1137/s009753970444658xopenalex-snapshot
Derandomizing Homomorphism Testing in General Groups
inferred← citeshttps://doi.org/10.1137/s0895480100380458openalex-snapshot
The Nonapproximability of Non-Boolean Predicates
inferred← citeshttps://doi.org/10.1145/1007352.1007421openalex-snapshot
Derandomizing homomorphism testing in general groups
inferred← citeshttps://doi.org/10.1145/1067309.1067318openalex-snapshot
Guest column: inapproximability results via Long Code based PCPs
inferred← citeshttps://doi.org/10.1145/1132516.1132519openalex-snapshot
Gowers uniformity, influence of variables, and PCPs
inferred← citeshttps://doi.org/10.1145/1806689.1806725openalex-snapshot
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
inferred← citeshttps://doi.org/10.1145/2213977.2214074openalex-snapshot
Nearly complete graphs decomposable into large induced matchings and their applications
inferred← citeshttps://doi.org/10.1145/2462896.2462897openalex-snapshot
On the usefulness of predicates
inferred← citeshttps://doi.org/10.1145/2488608.2488665openalex-snapshot
Approximation resistance from pairwise independent subgroups
inferred← citeshttps://doi.org/10.1145/2611462.2611493openalex-snapshot
On the power of the congested clique model
inferred← citeshttps://doi.org/10.1145/2629620openalex-snapshot
Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
inferred← citeshttps://doi.org/10.1145/2873054openalex-snapshot
Approximation Resistance from Pairwise-Independent Subgroups
inferred← citeshttps://doi.org/10.1145/3293611.3331625openalex-snapshot
Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling
inferred← citeshttps://doi.org/10.1145/3357713.3384275openalex-snapshot
All non-trivial variants of 3-LDT are equivalent
inferred← citeshttps://doi.org/10.1145/3382734.3405732openalex-snapshot
Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets
inferred← citeshttps://doi.org/10.1145/3450524openalex-snapshot
SETH-based Lower Bounds for Subset Sum and Bicriteria Path
inferred← citeshttps://doi.org/10.1145/3564246.3585110openalex-snapshot
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
inferred← citeshttps://doi.org/10.1145/3778165openalex-snapshot
Property Testing with Online Adversaries
inferred← citeshttps://doi.org/10.1145/780542.780631openalex-snapshot
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
inferred← citeshttps://doi.org/10.37236/249openalex-snapshot
Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2021.19openalex-snapshot
Beating Two-Thirds For Random-Order Streaming Matching
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2019.54openalex-snapshot
On The Communication Complexity of High-Dimensional Permutations
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2022.90openalex-snapshot
Sublinear-Time Computation in the Presence of Online Erasures
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2009.1823openalex-snapshot
Testing Linear-Invariant Non-Linear Properties
inferred← citeshttps://doi.org/10.48550/arxiv.0811.1922openalex-snapshot
A Hypergraph Dictatorship Test with Perfect Completeness
inferred← citeshttps://doi.org/10.48550/arxiv.1111.0253openalex-snapshot
Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications
inferred← citeshttps://doi.org/10.48550/arxiv.1204.5662openalex-snapshot
On the Usefulness of Predicates
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.