On the public citation graph
Derandomized graph products
0 signed · 158 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/978-1-4684-2001-2_9openalex-snapshot
Reducibility among Combinatorial Problems
inferredcites →https://doi.org/10.1007/978-3-540-68279-0_8openalex-snapshot
Reducibility Among Combinatorial Problems
inferredcites →https://doi.org/10.1007/bf01940870openalex-snapshot
Simulating BPP using a general weak random source
inferredcites →https://doi.org/10.1016/0012-365x(88)90189-6openalex-snapshot
Explicit construction of linear sized tolerant networks
inferredcites →https://doi.org/10.1016/0022-0000(81)90040-4openalex-snapshot
Explicit constructions of linear-sized superconcentrators
inferredcites →https://doi.org/10.1016/0022-0000(91)90023-xopenalex-snapshot
Optimization, approximation, and complexity classes
inferredcites →https://doi.org/10.1016/0304-3975(94)00254-gopenalex-snapshot
The complexity and approximability of finding maximum feasible subsystems of linear relations
inferredcites →https://doi.org/10.1016/0890-5401(92)90056-lopenalex-snapshot
On the complexity of approximating the independent set problem
inferredcites →https://doi.org/10.1109/fscs.1990.89577openalex-snapshot
Randomness in interactive proofs
inferredcites →https://doi.org/10.1109/sfcs.1989.63449openalex-snapshot
Dispersers, deterministic amplification, and weak random sources
inferredcites →https://doi.org/10.1109/sfcs.1989.63466openalex-snapshot
Graph products and chromatic numbers
inferredcites →https://doi.org/10.1109/sfcs.1991.185341openalex-snapshot
Approximating clique is almost NP-complete
inferredcites →https://doi.org/10.1109/sfcs.1991.185351openalex-snapshot
Simulating BPP using a general weak random source
inferredcites →https://doi.org/10.1109/sfcs.1991.185397openalex-snapshot
Better expansion for Ramanujan graphs
inferredcites →https://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferredcites →https://doi.org/10.1109/sfcs.1992.267824openalex-snapshot
Probabilistic checking of proofs; a new characterization of NP
inferredcites →https://doi.org/10.1109/sfcs.1993.366815openalex-snapshot
The hardness of approximate optima in lattices, codes, and systems of linear equations
inferredcites →https://doi.org/10.1145/28395.28410openalex-snapshot
Deterministic simulation in LOGSPACE
inferredcites →https://doi.org/10.2307/2004116openalex-snapshot
A Survey of Matrix Theory and Matrix Inequalities
inferredcites →https://doi.org/10.2307/2315999openalex-snapshot
A Survey of Matrix Theory and Matrix Inequalities.
inferredcites →https://doi.org/10.5555/314464.314570openalex-snapshot
Approximating maximum independent set in bounded degree graphs
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.20031openalex-snapshot
On the advantage over a random assignment
inferred← citeshttps://doi.org/10.1006/inco.2000.2884openalex-snapshot
Bounded Queries, Approximations, and the Boolean Hierarchy
inferred← citeshttps://doi.org/10.1006/inco.2002.3148openalex-snapshot
Scalable Secure Storage When Half the System Is Faulty
inferred← citeshttps://doi.org/10.1006/jcss.1998.1587openalex-snapshot
Zero Knowledge and the Chromatic Number
inferred← citeshttps://doi.org/10.1007/0-387-23830-1_3openalex-snapshot
Probabilistic Verification and Non-Approximability
inferred← citeshttps://doi.org/10.1007/11424925_22openalex-snapshot
Differential Approximation of min sat, max sat and Related Problems
inferred← citeshttps://doi.org/10.1007/3-540-45022-x_49openalex-snapshot
Scalable Secure Storage when Half the System Is Faulty
inferred← citeshttps://doi.org/10.1007/3-540-46784-x_10openalex-snapshot
Induced Matchings in Regular Graphs and Trees
inferred← citeshttps://doi.org/10.1007/3-540-48523-6_17openalex-snapshot
On Some Tighter Inapproximability Results (Extended Abstract)
inferred← citeshttps://doi.org/10.1007/3-540-48686-0_28openalex-snapshot
On the Complexity of Approximating Colored-Graph Problems Extended Abstract
inferred← citeshttps://doi.org/10.1007/978-1-4614-7254-4_19openalex-snapshot
Paul Erdős’ Influence on Extremal Graph Theory
inferred← citeshttps://doi.org/10.1007/978-1-4757-3023-4_1openalex-snapshot
The Maximum Clique Problem
inferred← citeshttps://doi.org/10.1007/978-1-4757-3613-7_23openalex-snapshot
Opportunity Cost Algorithms for Combinatorial Auctions
inferred← citeshttps://doi.org/10.1007/978-3-030-39479-0_14openalex-snapshot
Improved (In-)Approximability Bounds for d-Scattered Set
inferred← citeshttps://doi.org/10.1007/978-3-031-09574-0_21openalex-snapshot
How Much Randomness is Needed to Convert MA Protocols to AM Protocols?
inferred← citeshttps://doi.org/10.1007/978-3-032-13562-9_36openalex-snapshot
Colored Node Kayles: Algorithms and Computational Complexity
inferred← citeshttps://doi.org/10.1007/978-3-032-18230-2_5openalex-snapshot
Multi-level Graph Fusion for Intelligent Document Merging: Integrating $$\textsf{FPT}$$ Algorithms with Large Language Models: Merge2Docs
inferred← citeshttps://doi.org/10.1007/978-3-319-25258-2_8openalex-snapshot
Online Admission Control and Embedding of Service Chains
inferred← citeshttps://doi.org/10.1007/978-3-540-30551-4_42openalex-snapshot
On the Hardness and Easiness of Random 4-SAT Formulas
inferred← citeshttps://doi.org/10.1007/978-3-540-45198-3_8openalex-snapshot
On the Complexity of Approximating k-Dimensional Matching
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_66openalex-snapshot
Uniform Budgets and the Envy-Free Pricing Problem
inferred← citeshttps://doi.org/10.1007/978-3-540-74126-8_16openalex-snapshot
Topology Independent Protein Structural Alignment
inferred← citeshttps://doi.org/10.1007/978-3-540-75488-6_8openalex-snapshot
On Approximating Minimum Infrequent and Maximum Frequent Sets
inferred← citeshttps://doi.org/10.1007/978-3-540-93980-1_13openalex-snapshot
On Lagrangian Relaxation and Subset Selection Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_46openalex-snapshot
Constructive Proofs of Concentration Bounds
inferred← citeshttps://doi.org/10.1007/978-3-642-21934-4_5openalex-snapshot
Wireless Sensor Network’s Lifetime Maximization Problem in Case of Given Set of Covers
inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_36openalex-snapshot
Optimal Hitting Sets for Combinatorial Shapes
inferred← citeshttps://doi.org/10.1007/978-3-662-43948-7_40openalex-snapshot
Demand Queries with Preprocessing
inferred← citeshttps://doi.org/10.1007/bf01581168openalex-snapshot
Approximating the independence number via theϑ-function
inferred← citeshttps://doi.org/10.1007/bf02523693openalex-snapshot
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
inferred← citeshttps://doi.org/10.1007/bf02773611openalex-snapshot
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
inferred← citeshttps://doi.org/10.1007/bfb0053959openalex-snapshot
Approximations of independent sets in graphs
inferred← citeshttps://doi.org/10.1007/pl00021187openalex-snapshot
Large Sets of Nearly Orthogonal Vectors
inferred← citeshttps://doi.org/10.1007/s00037-006-0205-6openalex-snapshot
On the complexity of approximating k-set packing
inferred← citeshttps://doi.org/10.1007/s00037-010-0287-zopenalex-snapshot
A New Characterization of ACC0 and Probabilistic CC0
inferred← citeshttps://doi.org/10.1007/s00037-013-0076-6openalex-snapshot
Randomness Buys Depth for Approximate Counting
inferred← citeshttps://doi.org/10.1007/s00453-008-9175-1openalex-snapshot
On the Longest Common Rigid Subsequence Problem
inferred← citeshttps://doi.org/10.1007/s00453-013-9766-3openalex-snapshot
Inequalities for the Number of Walks in Graphs
inferred← citeshttps://doi.org/10.1007/s00453-020-00729-zopenalex-snapshot
Greed is Good for Deterministic Scale-Free Networks
inferred← citeshttps://doi.org/10.1007/s10458-011-9168-3openalex-snapshot
Multiagent task allocation in social networks
inferred← citeshttps://doi.org/10.1016/0304-3975(94)00254-gopenalex-snapshot
The complexity and approximability of finding maximum feasible subsystems of linear relations
inferred← citeshttps://doi.org/10.1016/j.artint.2023.103881openalex-snapshot
Designing menus of contracts efficiently: The power of randomization
inferred← citeshttps://doi.org/10.1016/j.dam.2020.10.001openalex-snapshot
On Lagrangian relaxation for constrained maximization and reoptimization problems
inferred← citeshttps://doi.org/10.1016/j.ejor.2005.04.057openalex-snapshot
Differential approximation of min sat, max sat and related problems
inferred← citeshttps://doi.org/10.1016/j.ic.2014.12.013openalex-snapshot
Local correctability of expander codes
inferred← citeshttps://doi.org/10.1016/j.ipl.2005.08.012openalex-snapshot
On the hardness of approximating Max-Satisfy
inferred← citeshttps://doi.org/10.1016/j.jcss.2009.01.002openalex-snapshot
On approximating four covering and packing problems
inferred← citeshttps://doi.org/10.1016/j.jfa.2005.11.003openalex-snapshot
Logarithmic reduction of the level of randomness in some probabilistic geometric constructions
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.05.023openalex-snapshot
Completeness in approximation classes beyond APX
inferred← citeshttps://doi.org/10.1016/j.tcs.2016.04.006openalex-snapshot
Traveling salesman problems in temporal graphs
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00226-0openalex-snapshot
Improved non-approximability results for minimum vertex cover with density constraints
inferred← citeshttps://doi.org/10.1088/1367-2630/ac3a84openalex-snapshot
Large violations in Kochen Specker contextuality and their applications
inferred← citeshttps://doi.org/10.1090/s0273-0979-06-01126-8openalex-snapshot
Expander graphs and their applications
inferred← citeshttps://doi.org/10.1093/imrn/rnw099openalex-snapshot
Large Deviations and Effective Equidistribution
inferred← citeshttps://doi.org/10.1103/physreva.92.062125openalex-snapshot
Quantum theory allows for absolute maximal contextuality
inferred← citeshttps://doi.org/10.1109/ccc.1996.507690openalex-snapshot
Zero knowledge and the chromatic number
inferred← citeshttps://doi.org/10.1109/ccc.2009.15openalex-snapshot
A New Characterization of ACC^0 and Probabilistic CC^0
inferred← citeshttps://doi.org/10.1109/ccc.2011.20openalex-snapshot
Explicit Dimension Reduction and Its Applications
inferred← citeshttps://doi.org/10.1109/focs.2004.59openalex-snapshot
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique
inferred← citeshttps://doi.org/10.1109/focs.2008.41openalex-snapshot
Broadcasting with Side Information
inferred← citeshttps://doi.org/10.1109/focs.2009.27openalex-snapshot
Distance Oracles for Sparse Graphs
inferred← citeshttps://doi.org/10.1109/focs.2011.39openalex-snapshot
Lexicographic Products and the Power of Non-linear Network Coding
inferred← citeshttps://doi.org/10.1109/iembs.2004.1403795openalex-snapshot
Order independent structural alignment of circularly permuted proteins
inferred← citeshttps://doi.org/10.1109/jproc.2020.2969687openalex-snapshot
Combinatorial Optimization of Graphical User Interface Designs
inferred← citeshttps://doi.org/10.1109/sfcs.1995.492571openalex-snapshot
Reductions, codes, PCPs, and inapproximability
inferred← citeshttps://doi.org/10.1109/sfcs.1995.492573openalex-snapshot
Free bits, PCPs and non-approximability-towards tight results
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743425openalex-snapshot
Probabilistically checkable proofs with low amortized query complexity
inferred← citeshttps://doi.org/10.1109/sfcs.2005.8openalex-snapshot
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications
inferred← citeshttps://doi.org/10.1137/090752353openalex-snapshot
Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems
inferred← citeshttps://doi.org/10.1137/090764190openalex-snapshot
Explicit Construction of a Small $\epsilon$-Net for Linear Threshold Functions
inferred← citeshttps://doi.org/10.1137/1.9781611973020.4openalex-snapshot
Inequalities for the Number of Walks in Graphs
inferred← citeshttps://doi.org/10.1137/1.9781611975994.39openalex-snapshot
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
inferred← citeshttps://doi.org/10.1137/16m1082421openalex-snapshot
Bi-Covering: Covering Edges with Two Small Subsets of Vertices
inferred← citeshttps://doi.org/10.1137/20m1379745openalex-snapshot
Deterministic Tensor Completion with Hypergraph Expanders
inferred← citeshttps://doi.org/10.1137/s009753970240118xopenalex-snapshot
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
inferred← citeshttps://doi.org/10.1137/s0097539794266407openalex-snapshot
On Unapproximable Versions of $NP$-Complete Problems
inferred← citeshttps://doi.org/10.1137/s0097539796302531openalex-snapshot
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
inferred← citeshttps://doi.org/10.1142/s0219199708002879openalex-snapshot
ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS
inferred← citeshttps://doi.org/10.1145/1132516.1132612openalex-snapshot
Linear degree extractors and the inapproximability of max clique and chromatic number
inferred← citeshttps://doi.org/10.1145/1329125.1329217openalex-snapshot
Distributed task allocation in social networks
inferred← citeshttps://doi.org/10.1145/1536414.1536502openalex-snapshot
Explicit construction of a small epsilon-net for linear threshold functions
inferred← citeshttps://doi.org/10.1145/2390176.2390182openalex-snapshot
Algorithms and complexity for periodic real-time scheduling
inferred← citeshttps://doi.org/10.1145/2488608.2488665openalex-snapshot
Approximation resistance from pairwise independent subgroups
inferred← citeshttps://doi.org/10.1145/274787.274791openalex-snapshot
Approximate graph coloring by semidefinite programming
inferred← citeshttps://doi.org/10.1145/2873054openalex-snapshot
Approximation Resistance from Pairwise-Independent Subgroups
inferred← citeshttps://doi.org/10.1145/3309697.3331519openalex-snapshot
The Segmentation-Thickness Tradeoff in Online Marketplaces
inferred← citeshttps://doi.org/10.1145/3322205.3311089openalex-snapshot
The Segmentation-Thickness Tradeoff in Online Marketplaces
inferred← citeshttps://doi.org/10.1145/3490486.3538270openalex-snapshot
Designing Menus of Contracts Efficiently: The Power of Randomization
inferred← citeshttps://doi.org/10.1145/3561046openalex-snapshot
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors
inferred← citeshttps://doi.org/10.1145/3564246.3585238openalex-snapshot
Optimal Explicit Small-Depth Formulas for the Coin Problem
inferred← citeshttps://doi.org/10.1145/3717823.3718130openalex-snapshot
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
inferred← citeshttps://doi.org/10.1145/380752.380839openalex-snapshot
Non-approximability results for optimization problems on bounded degree instances
inferred← citeshttps://doi.org/10.1145/509907.509916openalex-snapshot
On the advantage over a random assignment
inferred← citeshttps://doi.org/10.1145/509907.509985openalex-snapshot
Relations between average case complexity and approximation complexity
inferred← citeshttps://doi.org/10.1186/1471-2105-8-388openalex-snapshot
Topology independent protein structural alignment
inferred← citeshttps://doi.org/10.1214/ejp.v17-2229openalex-snapshot
Exit time tails from pairwise decorrelation in hidden Markov chains, with applications to dynamical percolation
inferred← citeshttps://doi.org/10.1287/msom.2024.0832openalex-snapshot
Dynamic Pricing with Menu Costs: Approximation Schemes and Applications to Grocery Retail
inferred← citeshttps://doi.org/10.1561/0400000113openalex-snapshot
Algorithmic Contract Theory: A Survey
inferred← citeshttps://doi.org/10.3390/a11010010openalex-snapshot
Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2022.90openalex-snapshot
On Lower Bounds of Approximating Parameterized $k$-Clique
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2021.10openalex-snapshot
The Strongish Planted Clique Hypothesis and Its Consequences
inferred← citeshttps://doi.org/10.48550/arxiv.1004.1379openalex-snapshot
Index coding via linear programming
inferred← citeshttps://doi.org/10.48550/arxiv.1304.8129openalex-snapshot
Local Correctability of Expander Codes
inferred← citeshttps://doi.org/10.48550/arxiv.1503.02880openalex-snapshot
On the Approximability of Independent Set Problem on Power Law Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.1512.06736openalex-snapshot
On Lagrangian Relaxation and Reoptimization Problems
inferred← citeshttps://doi.org/10.48550/arxiv.1711.11392openalex-snapshot
Two-sided Facility Location
inferred← citeshttps://doi.org/10.48550/arxiv.math/0410560openalex-snapshot
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
inferred← citeshttps://doi.org/10.48550/arxiv.math/0703742openalex-snapshot
Generalized zig-zag products of regular digraphs and bounds on their spectral expansions
inferred← citeshttps://doi.org/10.5555/640160.640166openalex-snapshot
Improved approximations of independent sets in bounded-degree graphs via subgraph removal
inferred← citeshttps://doi.org/10.70675/5040d861zebb7z424bz8a75z37fe027a71beopenalex-snapshot
Structurally Parameterized Tight Bounds and Approximation for Generalizations of Independence and Domination
inferred← citeshttps://doi.org/10.7155/jgaa.00621openalex-snapshot
Improved (In-)Approximability Bounds for d-Scattered Set
inferred← citeshttps://doi.org/10.7282/t3rn3749openalex-snapshot
New computational aspects of discrepancy theory
inferred← citeshttps://doi.org/10.82444/warw.33642091openalex-snapshot
Randomised techniques in combinatorial algorithmics
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.