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.
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/0471722154openalex-snapshot
The Probabilistic Method
inferredcites →https://doi.org/10.1006/jcss.2001.1747openalex-snapshot
Linear-Consistency Testing
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.1016/s0022-0000(05)80043-1openalex-snapshot
Hardness vs randomness
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.biblioopenalex-snapshot
General Bibliography
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/11538462_12openalex-snapshot
Beating a Random Assignment
inferred← citeshttps://doi.org/10.1007/11538462_31openalex-snapshot
Testing Periodicity
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/ccc.2012.18openalex-snapshot
On the Usefulness of Predicates
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/100791075openalex-snapshot
Sublinear Time Algorithms
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/1060590.1060614openalex-snapshot
Efficient testing of 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.18452/16375openalex-snapshot
Sparse instances of hard problems
inferred← citeshttps://doi.org/10.37236/249openalex-snapshot
Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma
inferred← citeshttps://doi.org/10.4086/toc.2005.v001a007openalex-snapshot
inferred← citeshttps://doi.org/10.4086/toc.2011.v007a006openalex-snapshot
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.