yusuke1997/dblp-id-title huggingface dataset:
36th Annual Symposium on Foundations of Computer Science, FOCS 1995, Milwaukee, Wisconsin, USA, 23-25 October 1995
Hardness of Minimizing and Learning DNF Expressions
Fast Algorithms for Matrix Normal Forms
Approximate Modularity
The Constant Inapproximability of the Parameterized Dominating Set Problem
Top-Down Lower Bounds for Depth 3 Circuits
Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant
Hierarchies of memory limited computations
Single-Source Unsplittable Flow
Finding k-cuts within Twice the Optimal
Communication complexity of Nash equilibrium in potential games (extended abstract)
Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk
Almost Optimal Inapproximability of Multidimensional Packing Problems
Improved Hardness of Approximating k-Clique under ETH
Dynamic treewidth
Partially Symmetric Functions Are Efficiently Isomorphism-Testable
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA
Collaborative Top Distribution Identifications with Limited Interaction (Extended Abstract)
Boolean Unateness Testing with Õ(n 3/4 ) Adaptive Queries
Constructing Generalized Universal Traversing Sequences of Polynomial Size for Graphs with Small Diameter (Extended Abstract)
Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
Pseudorandom Bits for Polynomials
Gaussian Approximation of Convex Sets by Intersections of Halfspaces
51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, October 23-26, 2010
Stateless Cryptographic Protocols
An Optimal Parallel Algorithm for Integer Sorting
A Linear Time Algorithm for Deciding Security
Context-Free Language Processing in Time n^3
Highly Fault-Tolerant Sorting Circuits
Planning and Learning in Permutation Groups
(Acyclic) JobShops are Hard to Approximate
Characterization of the Synchronization Languages for PV Systems
Fitting tree metrics: Hierarchical clustering and Phylogeny
Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm
Simple Deterministic Languages
Optimality of the Johnson-Lindenstrauss Lemma
Filtering Search: A New Approach to Query-Answering
The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Resolving the Optimal Metric Distortion Conjecture
Algebraic Methods for Interactive Proof Systems
On the Impossibility of Obfuscation with Auxiliary Input
Set constraints with projections are in NEXPTIME
Designing Networks Incrementally
Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards
The Exact Time Required to Perform Generalized Addition
31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II
Fast Solution of Some Random NP-Hard Problems
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs
Planting Undetectable Backdoors in Machine Learning Models : [Extended Abstract]
Computing with Very Weak Random Sources
45th Symposium on Foundations of Computer Science, FOCS 2004, Rome, Italy, October 17-19, 2004, Proceedings
Testing Juntas
Arithmetic Circuits: A Chasm at Depth Three
NEEXP is Contained in MIP
Competitive Flow Time Algorithms for Polyhedral Scheduling
The Power of Quantum Systems on a Line
Generalization of Self-Dual and Self-Complementary Dual Functions
Improved Bounds for Sampling Colorings
A Transform Approach to Logic Design
The supersingular isogeny path and endomorphism ring problems are equivalent
PPSZ is better than you think
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
Categories for Fixpoint-Semantics
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits
Local Management of a Global Resource in a Communication Network
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
Parallel Computational Geometry (Extended Abstract)
Lower Bounds for the Signature Size of Incremental Schemes
Analysis of Sorting Algorithms
Testing Properties of Sparse Images
Halvers and Expanders
Permanent and Determinant
Coded trace reconstruction in a constant number of traces
Maximizing Quadratic Programs: Extending Grothendieck's Inequality
On formalisms for Turing machines
Norm of the inverse of a random matrix
Accidental Algorithms
Faster Minimum k-cut of a Simple Graph
A Robust Sparse Fourier Transform in the Continuous Setting
Visibility-Polygon Search and Euclidean Shortest Paths
Collapsing Degrees (Extended Abstract)
Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
Bounds on Selection Networks
Axiomatic Equivalence of Programs with Structured Variables
Processor-Efficient Parallel Solution of Linear Systems II: The Positive Characteristic and Singular Cases (Extended Abstract)
The ESPRIT Algorithm Under High Noise: Optimal Error Scaling and Noisy Super-Resolution
Pipelining Computations in a Tree of Processors (Preliminary Version)
A Recognition Algorithm for Deterministic CFLS optimal in Time and Space
Factoring Polynomials over Finite Fields
On Robustness to k-Wise Independence of Optimal Bayesian Mechanisms
Random Projection: A New Approach to VLSI Layout
Fuzzy Star Functions, Probabilistic Automata and Their Approximation by Nonprobabilistic Automata
The Complexity of Dynamic Least-Squares Regression
Planar Graphs have Bounded Queue-Number
On the Power of Homogeneous Depth 4 Arithmetic Circuits
Randomness-Efficient Oblivious Sampling
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
Minimizing Congestion in General Networks
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
Planar Realizations of Nonlinear Davenport-Schinzel Sequences by Segments
A Parameterized Approximation Scheme for Min $k$-Cut
Improving the Bounds on Optimal Merging
A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems (Extended Abstract)
Polylogarithmic Guarantees for Generalized Reordering Buffer Management
Better Lower Bounds on Detecting Affine and Spherical Degeneracies
Polynomial-Time Algorithms for Permutation Groups
32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1-4, 1991
Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis
Simplification of Nested Radicals
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
Tight Quantum Time-Space Tradeoffs for Function Inversion
Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications
On Pointers versus Addresses (Extended Abstract)
Bounds on the Complexity of the Longest Common Subsequence Problem (Extended Abstract)
Extreme-Value Theorems for Optimal Multidimensional Pricing
19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978
Resolving Message Complexity of Byzantine Agreement and beyond
Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders
The Power of Commutativity
Lower Bounds for the Stable Marriage Problem and its Variants
All-Pairs Shortest Paths in O(n 2 ) Time with High Probability
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
Oblivious Transfer with a Memory-Bounded Receiver
Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis
Efficient String Matching in the Presence of Errors
On Efficient Band Matrix Arithmetic
The Category-Theoretic Solution of Recursive Domain Equations (Extended Abstract)
Faster Tree Pattern Matching
Agnostic proper learning of monotone functions: beyond the black-box correction barrier
On the Communication Complexity of Approximate Fixed Points
How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems
Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems
Interactive Proofs for General Distribution Properties
Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time
Scheduling Multithreaded Computations by Work Stealing
A Data Structure for Orthogonal Range Queries
Satisfiability, Branch-Width and Tseitin Tautologies
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems
Sparse Graph Counting and Kelley-Meka Bounds for Binary Systems
Computing the Determinant and Smith Form of an Integer Matrix
Bandits with Knapsacks
Optimal Power-Down Strategies
The Complexity of the Pigeonhole Principle
Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem
Hard-Core Distributions for Somewhat Hard Problems
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure
A New Algebraic Method for Robot Motion Planning and Real Geometry
The synthesis of cascade switching circuits
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting
Lower Bounds for Non-Black-Box Zero Knowledge
A Decision Procedure for Unitary Linear Quantum Cellular Automata
The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels
Bijective A-Transducers
Beating Simplex for Fractional Packing and Covering Linear Programs
The Complexity of General-Valued CSPs
A Stronger Bound for Linear 3-LCC
Almost Orthogonal Linear Codes are Locally Testable
Exponential Lower Bounds for Monotone Span Programs
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
AdWords and Generalized On-line Matching
Improved Approximations for Shallow-Light Spanning Trees
Efficient Computation of Euclidean Shortest Paths in the Plane
Cryptography in NC 0
Isotropic PCA and Affine-Invariant Clustering
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication
The Power of Linear Estimators
Languages that Are Easier than their Proofs
Dynamic Speed Scaling to Manage Energy and Temperature
13th Annual Symposium on Switching and Automata Theory, College Park, Maryland, USA, October 25-27, 1972
Bounds on the Evaluation Time for Rational Polynomials
Covering Polygons is Even Harder
Can you beat treewidth?
Local Search in Smooth Convex Sets
Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques
Distributed Reactive Systems Are Hard to Synthesize
Output Sufficient Modules for Uniform Decomposition of Synchronous Sequential Circuits
The Effect of the Field of Constants on the Number of Multiplication
A Semantic Characterization of Full Abstraction for Typed Lambda Calculi
Program Invariants as Fixed Points (Preliminary Reports)
Structure of Undecidable Problems in Automata Theory
A Dichotomy for Real Boolean Holant Problems
Multiparty Computation with Faulty Majority (Extended Announcement)
State-calculable stochastic sequential machines, equivalences, and events
On a Search Problem Related to Branch-and-Bound Procedures
No Sorting? Better Searching!
Reconstructing Algebraic Functions from Mixed Data
Asynchronous Sequential Circuits with (2,1) Type State Assignments
On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis
6th Annual Symposium on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan, USA, October 6-8, 1965
Canonical Forms for Matrix Tuples in Polynomial Time
Multilinear-NC neq Multilinear-NC
Geometric Intersection Problems
Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries
Fooling Intersections of Low-Weight Halfspaces
Parsing Algorithms with Backtrack
Matching with Our Eyes Closed
A Unified Continuous Greedy Algorithm for Submodular Maximization
Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method
Towards a Proof of the Fourier-Entropy Conjecture?
On the linearity of sequential machines
On Simultaneous Resource Bounds (Preliminary Version)
Computing ears and branchings in parallel
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination
The Complexity of Searching a Graph (Preliminary Version)
Polynomial Data Structure Lower Bounds in the Group Model
Noncryptographic Selection Protocols
Reverse Mathematics of Complexity Lower Bounds
A Deterministic Algorithm for Counting Colorings with 2-Delta Colors
Nearly Optimal Pseudorandomness From Hardness
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications
An O(n^1+epsilon log b) Algorithm for the Complex Roots Problem
Some unsolved problems in switching theory
Three Layers Are Enough
Universally Composable Security: A New Paradigm for Cryptographic Protocols
A Polynomial-Time Algorithm for the Perfect Phylogeny Problem when the Number of Character States is Fixed
An O(n^2 (m + n log n) log n) Min-Cost Flow Algorithm
Tighter Bounds on the Exact Complexity of String Matching (Extended Abstract)
Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography
Vertex Sparsifiers and Abstract Rounding Algorithms
Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs
Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing
Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture
A Decidability Result for a Second Order Process Logic
Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems
The zero-rate threshold for adversarial bit-deletions is less than 1/2
Polynomial Calculus Space and Resolution Width
A Spectral Approach to Lower Bounds
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
Spectral Partitioning of Random Graphs
NP Trees and Carnap's Modal Logic
Increasing the Size of a Network by a Constant Factor Can Increase Performance by More Than a Constant Factor
Tight Bounds for Quantum State Certification with Incoherent Measurements
3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
Complete Linear Proofs of Systems of Linear Inequalities
Hardware Complexity and Parallel Computation (Preliminary Version)
Towards a Characterization of Truthful Combinatorial Auctions
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
Fooling Constant-Depth Threshold Circuits (Extended Abstract)
Structure and Randomness in Combinatorics
Maximizing Determinants under Matroid Constraints
Lovász's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications
A Method for Factoring the Action of Asynchronous Circuits
On statistical inference when fixed points of belief propagation are unstable
Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic
Randomised Composition and Small-Bias Minimax
Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract)
Period-Time Tradeoffs for VLSI Models with Delay (Preliminary Version)
Threshold gate realizations of logical functions with don't cares
Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game
Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails
Fast Parallel Matrix Inversion Algorithms
Random graph models for the web graph
Machine Minimization for Scheduling Jobs with Interval Constraints
Some Techniques for Proving Certain Simple Programs Optimal
An Optimal Lower Bound on the Number of Variables for Graph Identification
Lempel-Ziv (LZ77) Factorization in Sublinear Time
Integer programs with bounded subdeterminants and two nonzeros per row
Pseudorandom Generators for Regular Branching Programs
Applications of Ramsey's Theorem to Decision Trees Complexity (Preliminary Version)
Stability Yields a PTAS for k-Median and k-Means Clustering
Deciding Properties of Nonregular Programs (Preliminary Version)
Efficient Exponentiation in Finite Fields (Extended Abstract)
Infinite sequences and finite machines
A Kinetic Framework for Computational Geometry
Polynomial Representations of Threshold Functions and Algorithmic Applications
Reed-Muller Codes Polarize
Black-Box Randomized Reductions in Algorithmic Mechanism Design
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters
Optimization of the Sherrington-Kirkpatrick Hamiltonian
Efficient Approximation of Fractional Hypertree Width
An Infinite Hierarchy of Context-Free Languages
On Learning and Testing Dynamic Environments
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed
On the Complexity of Fixed Parameter Problems (Extended Abstract)
k-Wise Independent Random Graphs
Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary)
External-Memory Computational Geometry (Preliminary Version)
Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods
Entangled Games are Hard to Approximate
Correlated Pseudorandom Functions from Variable-Density LPN
Sink Equilibria and Convergence
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes
Frugal and Truthful Auctions for Vertex Covers, Flows and Cuts
Performance Analysis of Dynamic Network Processes
Towards derandomising Markov chain Monte Carlo
Optimal Algorithms for Bounded Weighted Edit Distance
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise
On the Optimality of Planar and Geometric Approximation Schemes
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
Testability of relations between permutations
Algorithms for the Generalized Sorting Problem
Always Good Turing: Asymptotically Optimal Probability Estimation
Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem
Solving the Hamilton cycle problem fast on average
On Non-Approximability for Quadratic Programs
Computing with Polynomials Given By Black Boxes for Their Evaluation: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators
On the Star Height of Regular Events
Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems
Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes
Fixed-Point Extensions of First-Order Logic
Geometric Complexity Theory V: Equivalence between Blackbox Derandomization of Polynomial Identity Testing and Derandomization of Noether's Normalization Lemma
Heat & Dump: Competitive Distributed Paging
General Framework for Metric Optimization Problems with Delay or with Deadlines
The Equivalence Problem for Deterministic Two-Way Sequential Transducers Is Decidable
Automatic Verification of Probabilistic Concurrent Finite-State Programs
The Parity of Directed Hamiltonian Cycles
Convergence to Equilibrium in Local Interaction Games
On Clusterings - Good, Bad and Spectral
Load Balancing in the L p Norm
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
A simple condition implying rapid mixing of single-site dynamics on spin systems
How to Pack Better than Best Fit: Tight Bounds for Average-Case On-Line Bin Packing
Towards a Better Approximation for Sparsest Cut?
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach
Topological constraints on interconnection-limited logic
Generic Oracles and Oracle Classes (Extended Abstract)
A Grammatical Characterization of Exponential-Time Languages
SDP gaps and UGC-hardness for MAXCUTGAIN
Hamiltonian Cycles in Solid Grid Graphs
The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices
The Vector Balancing Constant for Zonotopes
On the Existence of Algebraically Natural Proofs
Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract)
Approximate Hypergraph Partitioning and Applications
Throughput-Competitive On-Line Routing
Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version)
Computation of Algebraic Functions with Root Extractions
Dynamic Computational Geometry (Preliminary Version)
Approximability of all finite CSPs with linear sketches
The Asymptotic Order of the Random k -SAT Threshold
An Optimal Parallel Algorithm for Graph Planarity (Extended Abstract)
2nd Annual Symposium on Switching Circuit Theory and Logical Design, Detroit, Michigan, USA, October 17-20, 1961
A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks
The Mutual Exclusion Problem for Unreliable Processes: Preliminary Report
Knowledge-Preserving Interactive Coding
Approximating Geometric Knapsack via L-Packings
Randomness and the Density of Hard Problems
Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures
Ramanujan Graphs in Polynomial Time
Randomized Consensus in Expected O(n log ^2 n) Operations Per Processor
Towards the sampling Lovász Local Lemma
Evaluating Relational Expressions with Dense and Sparse Arguments
Reachability in Vector Addition Systems is Ackermann-complete
Simultaneous Resettability from One-Way Functions
Improved Approximation Algorithms for Large Matrices via Random Projections
Magic Functions
KKL, Kruskal-Katona, and Monotone Nets
Approximating Directed Multicuts
One-step replica symmetry breaking of random regular NAE-SAT
Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication
Adversarial Bandits with Knapsacks
Techniques for the diagnosis of switching circuit failures
The Minimum Equivalent DNF Problem and Shortest Implicants
An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs
An application of linear programming to the minimization of Boolean functions
Facility Location with Nonuniform Hard Capacities
Iteratively Realized Sequential Circuits: Further Considerations
Online Node-Weighted Steiner Tree and Related Problems
Asymptotically Fast Algorithms for Spherical and Related Transforms
On Representations by Low-Degree Polynomials
A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract)
Concentrated Regular Data Streams on Grids: Sorting and Routing Near to the Bisection Bound
Radio Network Coding Requires Logarithmic Overhead
Approximating Minimization Diagrams and Generalized Proximity Search
List-decodability with large radius for Reed-Solomon codes
Auctions with Severely Bounded Communication
Provably Good Mesh Generation
65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024
Mulltiplication of Polynomials over the Ring of Integers
Semantical Considerations on Floyd-Hoare Logic
Reducing Network Congestion and Blocking Probability Through Balanced Allocation
On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract)
Reversibility in monadic algebras and automata
Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs
Complexity of Flow Analysis, Inductive Assertion Synthesis and a Language Due to Dijkstra
On Self-Organizing Sequential Search Heuristics
Improved Decoding of Folded Reed-Solomon and Multiplicity Codes
ReSQueing Parallel and Private Stochastic Convex Optimization
On the Asymptotic Complexity of Matrix Multiplication (Extended Summary)
Quantum Lower Bounds for the Collision and the Element Distinctness Problems
Local Computation of Maximal Independent Set
Local Distributed Decision
Breaking of 1RSB in Random Regular MAX-NAE-SAT
Fault Detection Experiments for Asynchronous Sequential Machines
The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection