Parameterized Proof Complexity

No abstract is available for this paper.

• Publication year

  2007

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2007-10-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00037-010-0001-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation

  2007cited by this paper
• Improved Parameterized Upper Bounds for Vertex Cover

  2006cited by this paper
• Computing Nash Equilibria: Approximation and Smoothed Complexity

  2006cited by this paper
• Settling the Complexity of Two-Player Nash Equilibrium

  2006cited by this paper
• The complexity of computing a Nash equilibrium

  2006cited by this paper
• New upper and lower bounds for randomized and quantum local search

  2006cited by this paper
• Invitation to Fixed-Parameter Algorithms

  2006cited by this paper
• Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)

  2006cited by this paper
• On the Approximation and Smoothed Complexity of Leontief Market Equilibria

  2006cited by this paper
• Compendium of Parameterized Problems

  2006influential reference
• On the Quantum Query Complexity of Local Search in Two and Three Dimensions

  2006cited by this paper
• Leontief economies encode nonzero sum two-player games

  2006cited by this paper
• Parameterized Complexity Theory

  2006cited by this paper
• On the Black-Box Complexity of Sperner’s Lemma

  2005cited by this paper
• Simplicity is Beauty: Improved Upper Bounds for Vertex Cover

  2005influential reference
• On algorithms for discrete and approximate brouwer fixed points

  2005influential reference
• Quantum and Classical Query Complexities of Local Search Are Polynomially Related

  2004cited by this paper
• Exponentially many steps for finding a Nash equilibrium in a bimatrix game

  2004cited by this paper
• Approximate local search in combinatorial optimization

  2004cited by this paper
• Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time

  2004cited by this paper
• On the complexity of price equilibria

  2003cited by this paper
• Lower bounds for local search by quantum arguments

  2003cited by this paper
• Playing large games using simple strategies

  2003cited by this paper
• Proofs as Games

  2000cited by this paper
• A complexity gap for tree resolution

  1999influential reference
• Parameterized Complexity

  1998influential reference
• Which problems have strongly exponential complexity?

  1998cited by this paper
• Parameterized Complexity

  1998influential reference
• Resolution and the Weak Pigeonhole Principle

  1997influential reference
• Fixed-Parameter Tractability and Completeness II: On Completeness for W[1]

  1995cited by this paper
• Bounded arithmetic, propositional logic, and complexity theory

  1995cited by this paper
• The relative complexity of NP search problems

  1995cited by this paper
• Interior-point polynomial algorithms in convex programming

  1994cited by this paper
• On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence

  1994cited by this paper
• Integrated voice/data on a centralized switch node architecture for LAN with free round robin service strategy

  1993cited by this paper
• On Inefficient Proofs of Existence and Complexity Classes

  1992cited by this paper
• Algorithms in Combinatorial Geometry

  1987cited by this paper
• Exponential lower bounds for finding Brouwer fixed points

  1987cited by this paper
• How Easy is Local Search?

  1985cited by this paper
• A new polynomial-time algorithm for linear programming

  1984cited by this paper
• Minimization Algorithms and Random Walk on the $d$-Cube

  1983influential reference
• The Relative Efficiency of Propositional Proof Systems

  1979influential reference
• Probabilistic computations: Toward a unified measure of complexity

  1977cited by this paper
• The Computation of Economic Equilibria

  1974cited by this paper
• On the lengths of proofs in the propositional calculus (Preliminary Version)

  1974cited by this paper
• The computation of equilibrium prices

  1973cited by this paper
• HOW GOOD IS THE SIMPLEX ALGORITHM

  1970cited by this paper
• The Approximation of Fixed Points of a Continuous Mapping

  1967cited by this paper
• Equilibrium Points of Bimatrix Games

  1964cited by this paper
• EXISTENCE OF AN EQUILIBRIUM FOR A COMPETITIVE ECONOMY

  1954cited by this paper
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

  1952cited by this paper
• Equilibrium Points in N-Person Games.

  1950cited by this paper
• Neuer beweis für die invarianz der dimensionszahl und des gebietes

  1928cited by this paper
• Über Abbildung von Mannigfaltigkeiten

  1911cited by this paper

• Deep Learning-Based Dispatching Conflict Avoider in MEC Systems

  2025cites this paper
• Quantum Automating TC0-Frege Is LWE-Hard

  2024cites this paper
• Design of Task Distribution and Scheduling Strategies for Data Processingin the Internet of Things

  2024cites this paper
• The Riis Complexity Gap for QBF Resolution

  2024cites this paper
• Does Subset Sum Admit Short Proofs?

  2024cites this paper
• Online Approximation Scheme for Scheduling Heterogeneous Utility Jobs in Edge Computing

  2023cites this paper
• Preemptive Scheduling for Distributed Machine Learning Jobs in Edge-Cloud Networks

  2022cites this paper
• Improved Approximations for Unrelated Machine Scheduling

  2022cites this paper
• Reducing Average Job Completion Time for DAG-style Jobs by Adding Idle Slots

  2022cites this paper
• Flow time scheduling and prefix Beck-Fiala

  2022cites this paper
• Kernelization, Proof Complexity and Social Choice

  2021cites this paper
• SmartDis: Near-Optimal Task Scheduling in Multi-edge Networks

  2021cites this paper
• Online Job Scheduling on a Single Machine with General Cost Functions

  2021cites this paper
• Improving Learning-Based DAG Scheduling by Inserting Deliberate Idle Slots

  2021cites this paper
• Fixed-Parameter Tractability

  2021cites this paper
• Taming Tail Latency in Key-Value Stores: A Scheduling Perspective

  2021cites this paper
• Online Deadline-Aware Task Dispatching and Scheduling in Edge Computing

  2020cites this paper
• Strong intractability results for generalized convex recoloring problems

  2020cites this paper
• Online dispatching and scheduling of jobs with heterogeneous utilities in edge computing

  2020cites this paper
• Scheduling Flows on a Switch to Optimize Response Times

  2020cites this paper
• Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution

  2020cites this paper
• A Unifying Optimal Control Framework for Online Job Scheduling with General Cost Functions

  2019cites this paper
• An Optimal Control Framework for Online Job Scheduling with General Cost Functions

  2019cites this paper
• OnDisc: Online Latency-Sensitive Job Dispatching and Scheduling in Heterogeneous Edge-Clouds

  2019cites this paper
• On Communication Complexity of Fixed Point Computation

  2019cites this paper
• Joint Online Coflow Routing and Scheduling in Data Center Networks

  2019cites this paper
• Dedas: Online Task Dispatching and Scheduling with Bandwidth Constraint in Edge Computing

  2019cites this paper
• Clique is hard on average for regular resolution

  2018cites this paper
• Non-Preemptive Flow-Time Minimization via Rejections

  2018cites this paper
• Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models

  2018cites this paper
• A Modern View on Stability of Approximation

  2018cites this paper
• Improved Online Algorithm for Weighted Flow Time

  2017cites this paper
• Competitive Algorithms from Competitive Equilibria

  2017cites this paper
• Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations

  2017cites this paper
• Strong intractability of generalized convex recoloring problems

  2017cites this paper
• Online Min-Sum Flow Scheduling with Rejections

  2017cites this paper
• Theoretical Foundations of Team Matchmaking

  2017cites this paper
• Online job dispatching and scheduling in edge-clouds

  2017influential citation
• Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines

  2016cites this paper
• Partitioned Feasibility Tests for Sporadic Tasks on Heterogeneous Machines

  2016cites this paper
• Query Complexity of Approximate Nash Equilibria

  2016cites this paper
• O ct 2 01 4 Relativization makes contradictions harder for Resolution ✩

  2016influential citation
• Design of Scheduling Algorithms Using Game Theoretic Ideas

  2015cites this paper
• Scheduling in Bandwidth Constrained Tree Networks

  2015cites this paper
• Primal–Dual and Dual-Fitting Analysis of Online Scheduling Algorithms for Generalized Flow-Time Problems

  2015cites this paper
• Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints

  2014cites this paper
• Minimizing Flow-Time on Unrelated Machines

  2014influential citation
• SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors

  2014cites this paper
• Minimizing average flow-time under knapsack constraint

  2014cites this paper
• Succinct Non-Interactive Arguments via Linear Interactive Proofs

  2013cites this paper
• The complexity of proving that a graph is Ramsey

  2013cites this paper
• Recoloração convexa de grafos: algoritmos e poliedros

  2013cites this paper
• Relativization makes contradictions harder for Resolution

  2013influential citation
• Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling

  2013cites this paper
• Weighted Flowtime on Capacitated Machines

  2013cites this paper
• A characterization of tree-like Resolution size

  2013cites this paper
• Parameterized Proof Complexity and W[1]

  2012influential citation
• Parameterized Resolution with Bounded Conjunction

  2012influential citation
• Some Definitorial Suggestions for Parameterized Proof Complexity

  2012cites this paper
• Parameterized Complexity of Weighted Satisfiability Problems: Decision, Enumeration, Counting

  2012cites this paper
• Non-classical Aspects in Proof Complexity

  2012cites this paper
• The complexity of non-monotone markets

  2012cites this paper
• Resource augmentation for weighted flow-time explained by dual fitting

  2012influential citation
• Parameterized Bounded-Depth Frege Is not Optimal

  2011influential citation
• A W[1]-Completeness Result for Generalized Permutation Pattern Matching

  2011cites this paper
• New Extension of the Weil Bound for Character Sums with Applications to Coding

  2011cites this paper
• Proofs and Games Course Material

  2011influential citation
• On LP-based approximability for strict CSPs

  2011cites this paper
• Parameterized Complexity of DPLL Search Procedures

  2011cites this paper
• An online scalable algorithm for minimizing lk-norms of weighted flow time on unrelated machines

  2011cites this paper
• On scheduling in map-reduce and flow-shops

  2011cites this paper
• The Parameterized Complexity of K-flip Local Search for Sat and Max Sat the Parameterized Complexity of K-flip Local Search for Sat and Max Sat

  2011influential citation
• Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields

  2010cites this paper
• Different Approaches to Proof Systems

  2010cites this paper
• Hardness of Parameterized Resolution

  2010influential citation
• Makespan minimization in online scheduling with machine eligibility

  2010influential citation
• The Strength of Parameterized Tree-like Resolution

  2010influential citation
• A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games

  2010cites this paper
• Small-Bias Spaces for Group Products

  2009cites this paper
• Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability

  2009cites this paper
• Pseudorandom Bit Generators That Fool Modular Sums

  2009cites this paper
• A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation

  2009cites this paper
• The parameterized complexity of k-flip local search for SAT and MAX SAT

  2009influential citation
• Minimizing Average Flow-Time

  2009cites this paper
• On the Optimality of a Class of LP-based Algorithms

  2009cites this paper
• The Complexity of Boolean Functions in Different Characteristics

  2009cites this paper
• Optimal Testing of Reed-Muller Codes

  2009cites this paper
• A Competitive Algorithm for Minimizing Weighted Flow Time on Unrelated Machines with Speed Augmentation

  2009cites this paper
• Minimizing Average Flow Time on Unrelated Machines

  2009cites this paper
• Fixed-Parameter Tractability

  2009cites this paper
• Bounded Independence Fools Halfspaces

  2009cites this paper
• The Sum of D Small-Bias Generators Fools Polynomials of Degree D

  2008cites this paper
• Phase Transitions and Complexity of Weighted Satisfiability and Other Intractable Parameterized Problems

  2008cites this paper
• Matching algorithmic bounds for finding a Brouwer fixed point

  2008cites this paper
• Minimizing Total Flow-Time: The Unrelated Case

  2008cites this paper
• On the Asymptotic Nullstellensatz and Polynomial Calculus Proof Complexity

  2008cites this paper
• Matched Formulas and Backdoor Sets

  2007cites this paper
• Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems

  2007cites this paper
• Settling the complexity of computing two-player Nash equilibria

  2007influential citation
• Scheduling Flows and Coflows in Networks

  year unknowncites this paper