Luca Trevisan

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Near-Optimal NP-Hardness of Approximating Max k-CSP<sub>R</sub>.

[BibT_eX]

[DOI]

Preetum Nakkiran

Arthur Carvalho Walraven da Cunha

Theory Comput., 2022

An IoT Measurement System Based on LoRaWAN for Additive Manufacturing.

[BibT_eX]

[DOI]

Sensors, 2022

On the Multidimensional Random Subset Sum Problem.

[BibT_eX]

[DOI]

Luca Becchetti

CoRR, 2022

Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification.

[BibT_eX]

[DOI]

Antares Chen

Jonathan Shi

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Percolation and Epidemic Processes in One-Dimensional Small-World Networks - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the LATIN 2022: Theoretical Informatics, 2022

Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Lower Bounds for Max-Cut in H-Free Graphs via Semidefinite Programming.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Introducing The Theory Blogs Column.

[BibT_eX]

[DOI]

Bull. EATCS, 2021

Correlation Clustering Reconstruction in Semi-Adversarial Models.

[BibT_eX]

[DOI]

CoRR, 2021

Sharp Thresholds for a SIR Model on One-Dimensional Small-World Networks.

[BibT_eX]

[DOI]

CoRR, 2021

2020

From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Find Your Place: Simple Distributed Algorithms for Community Detection.

[BibT_eX]

[DOI]

Luca Becchetti

Emanuele Natale

Francesco Pasquale

SIAM J. Comput., 2020

Cut Sparsification of the Clique Beyond the Ramanujan Bound.

[BibT_eX]

[DOI]

Antares Chen

Jonathan Shi

CoRR, 2020

A New Algorithm for the Robust Semi-random Independent Set Problem.

[BibT_eX]

[DOI]

Theo McKenzie

Hermish Mehta

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Finding a Bounded-Degree Expander Inside a Dense One.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Lower Bounds for Max-Cut via Semidefinite Programming.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Consensus vs Broadcast, with and Without Noise (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Evaluation of LoRaWAN for Sensor Data Collection in an IIoT-based Additive Manufacturing Project.

[BibT_eX]

[DOI]

Proceedings of the 2020 IEEE International Instrumentation and Measurement Technology Conference, 2020

Subexponential LPs Approximate Max-Cut.

[BibT_eX]

[DOI]

Samuel B. Hopkins

Tselil Schramm

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

An IIoT System to Monitor 3D-Printed Artifacts via LoRaWAN Embedded Sensors.

[BibT_eX]

[DOI]

Proceedings of the 25th IEEE International Conference on Emerging Technologies and Factory Automation, 2020

2019

Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs.

[BibT_eX]

[DOI]

Jess Banks

CoRR, 2019

Optimal Lower Bounds for Sketching Graph Cuts.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

New Notions and Constructions of Sparsification for Graphs and Hypergraphs.

[BibT_eX]

[DOI]

Nikhil Bansal

Ola Svensson

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs.

[BibT_eX]

[DOI]

Charles Carlson

Alexandra Kolla

CoRR, 2018

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems.

[BibT_eX]

[DOI]

CoRR, 2018

Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise.

[BibT_eX]

[DOI]

CoRR, 2018

An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification.

[BibT_eX]

[DOI]

Nikhil Srivastava

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Average Whenever You Meet: Opportunistic Protocols for Community Detection.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

Simple dynamics for plurality consensus.

[BibT_eX]

[DOI]

Distributed Comput., 2017

Friend or Foe? Population Protocols can perform Community Detection.

[BibT_eX]

[DOI]

CoRR, 2017

An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs.

[BibT_eX]

[DOI]

Michele Borassi

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Learning Heavy Fourier Coefficients of Boolean Functions.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Almost Optimal Local Graph Clustering Using Evolving Sets.

[BibT_eX]

[DOI]

J. ACM, 2016

Approximation of non-boolean 2CSP.

[BibT_eX]

[DOI]

Guy Kindler

Alexandra Kolla

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Stabilizing Consensus with Many Opinions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Near-Optimal UGC-hardness of Approximating Max k-CSP_R.

[BibT_eX]

[DOI]

Preetum Nakkiran

Proceedings of the Approximation, 2016

2015

A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs.

[BibT_eX]

[DOI]

Theory Comput., 2015

Quantum lower bound for inverting a permutation with advice.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

[BibT_eX]

[DOI]

Aravindan Vijayaraghavan

David Witmer

John Wright

Electron. Colloquium Comput. Complex., 2015

Information spreading in dynamic graphs.

[BibT_eX]

[DOI]

Andrea Clementi

Riccardo Silvestri

Distributed Comput., 2015

Unique Games on the Hypercube.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2015

2014

Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010).

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities.

[BibT_eX]

[DOI]

James R. Lee

J. ACM, 2014

Partitioning into Expanders.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank

[BibT_eX]

[DOI]

CoRR, 2013

Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?

[BibT_eX]

[DOI]

CoRR, 2013

Simple Dynamics for Majority Consensus.

[BibT_eX]

[DOI]

CoRR, 2013

Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

A Derandomized Switching Lemma and an Improved Derandomization of AC0.

[BibT_eX]

[DOI]

Tongke Xue

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Max Cut and the Smallest Eigenvalue.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

A Derandomized Switching Lemma and an Improved Derandomization of AC0.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Better pseudorandom generators from milder pseudorandom restrictions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

On the One-Way Function Candidate Proposed by Goldreich.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Pseudorandomness and derandomization.

[BibT_eX]

[DOI]

XRDS, 2012

A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues

[BibT_eX]

[DOI]

CoRR, 2012

Multi-way spectral partitioning and higher-order cheeger inequalities.

[BibT_eX]

[DOI]

James R. Lee

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Approximating the Expansion Profile and Almost Optimal Local Graph Clustering.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Dense Model Theorems and Their Applications.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 8th Theory of Cryptography Conference, 2011

From Logarithmic Advice to Single-Bit Advice.

[BibT_eX]

[DOI]

Oded Goldreich

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010

The Program-Enumeration Bottleneck in Average-Case Complexity Theory.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Time Space Tradeoffs for Attacks against One-Way Functions and PRGs.

[BibT_eX]

[DOI]

Anindya De

Proceedings of the Advances in Cryptology, 2010

2009

Guest column: additive combinatorics and theoretical computer science.

[BibT_eX]

[DOI]

SIGACT News, 2009

Non-uniform attacks against one-way functions and PRGs.

[BibT_eX]

[DOI]

Anindya De

Electron. Colloquium Comput. Complex., 2009

Improved Pseudorandom Generators for Depth 2 Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Foreword.

[BibT_eX]

[DOI]

Chandra Chekuri

Algorithmica, 2009

Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

Pseudorandom Bit Generators That Fool Modular Sums.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

Extractors Using Hardness Amplification.

[BibT_eX]

[DOI]

Anindya De

Proceedings of the Approximation, 2009

2008

Learning Heavy Fourier Coefficients of Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Approximation Algorithms for Unique Games.

[BibT_eX]

[DOI]

Theory Comput., 2008

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Dense Subsets of Pseudorandom Sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Average-case Complexity.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Pseudorandomness and Average-Case Complexity Via Uniform Reductions.

[BibT_eX]

[DOI]

Comput. Complex., 2007

Fun with Sub-linear Time Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Fun with Algorithms, 4th International Conference, 2007

Amplifying Collision Resistance: A Complexity-Theoretic Treatment.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 2007

2006

On epsilon-biased generators in NC<sup>0</sup>.

[BibT_eX]

[DOI]

Elchanan Mossel

Amir Shpilka

Random Struct. Algorithms, 2006

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut.

[BibT_eX]

[DOI]

Grant Schoenebeck

Electron. Colloquium Comput. Complex., 2006

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.

[BibT_eX]

[DOI]

Grant Schoenebeck

Electron. Colloquium Comput. Complex., 2006

Pseudorandomness and Combinatorial Constructions

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Average-Case Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Lower bounds for linear locally decodable codes and private information retrieval.

[BibT_eX]

[DOI]

Comput. Complex., 2006

Pseudorandom walks on regular digraphs and the RL vs. L problem.

[BibT_eX]

[DOI]

Omer Reingold

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005

The approximability of non-Boolean satisfiability problems and restricted integer programming.

[BibT_eX]

[DOI]

Maria J. Serna

Fatos Xhafa

Theor. Comput. Sci., 2005

Bounds on the Efficiency of Generic Cryptographic Constructions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Approximating the Minimum Spanning Tree Weight in Sublinear Time.

[BibT_eX]

[DOI]

Bernard Chazelle

Ronitt Rubinfeld

SIAM J. Comput., 2005

Approximating Succinct MaxSat.

[BibT_eX]

[DOI]

Christian Schallhart

J. Log. Comput., 2005

Gowers Uniformity, Influence of Variables, and PCPs

[BibT_eX]

[DOI]

Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2005

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

[BibT_eX]

[DOI]

Omer Reingold

Electron. Colloquium Comput. Complex., 2005

On Worst-Case to Average-Case Reductions for NP Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Compression of Samplable Sources.

[BibT_eX]

[DOI]

David Zuckerman

Comput. Complex., 2005

On Hardness Amplification of One-Way Functions.

[BibT_eX]

[DOI]

Henry C. Lin

Hoeteck Wee

Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

On uniform amplification of hardness in NP.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Hierarchies for semantic classes.

[BibT_eX]

[DOI]

Lance Fortnow

Rahul Santhanam

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

The Complexity of Making Unique Choices: Approximating 1-in- k SAT.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Proceedings of the Approximation, 2005

2004

On Local Versus Global Satisfiability.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2004

Promise Hierarchies

[BibT_eX]

[DOI]

Lance Fortnow

Rahul Santhanam

Electron. Colloquium Comput. Complex., 2004

From logarithmic advice to single-bit advice

[BibT_eX]

[DOI]

Oded Goldreich

Electron. Colloquium Comput. Complex., 2004

Inapproximability of Combinatorial Optimization Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Some Applications of Coding Theory in Computational Complexity

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Notions of Reducibility between Cryptographic Primitives.

[BibT_eX]

[DOI]

Omer Reingold

Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

A Note on Approximate Counting for k-DNF.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2004

Pseudorandomness - Part II.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity Theory., 2004

2003

On epsilon-Biased Generators in NC0

[BibT_eX]

[DOI]

Elchanan Mossel

Amir Shpilka

Electron. Colloquium Comput. Complex., 2003

List Decoding Using the XOR Lemma

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

An epsilon-Biased Generator in NC0

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

On e-Biased Generators in NC0.

[BibT_eX]

[DOI]

Elchanan Mossel

Amir Shpilka

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Error-Correcting Codes in Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002

A Note on Deterministic Approximate Counting for k-DNF

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

Lower Bounds for Testing Bipartiteness in Dense Graphs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

Counting Distinct Elements in a Data Stream.

[BibT_eX]

[DOI]

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.

[BibT_eX]

[DOI]

Kenji Obata

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Streaming Computation of Combinatorial Objects.

[BibT_eX]

[DOI]

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Pseudorandom Generators without the XOR Lemma.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

Extractors and pseudorandom generators.

[BibT_eX]

[DOI]

J. ACM, 2001

On Weighted vs Unweighted Versions of Combinatorial Optimization Problems.

[BibT_eX]

[DOI]

Riccardo Silvestri

Inf. Comput., 2001

Three Theorems regarding Testing Graph Properties.

[BibT_eX]

[DOI]

Oded Goldreich

Electron. Colloquium Comput. Complex., 2001

Approximating layout problems on random graphs.

[BibT_eX]

[DOI]

Discret. Math., 2001

Non-approximability results for optimization problems on bounded degree instances.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Error-Correcting Codes and Pseudorandom Projections.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

2000

A complexity analysis of bisimilarity for value-passing processes.

[BibT_eX]

[DOI]

Michele Boreale

Theor. Comput. Sci., 2000

Gadgets, Approximation, and Linear Programming.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

The Approximability of Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

On Approximation Scheme Preserving Reducibility and Its Applications.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2000

Lower Bounds on the Efficiency of Generic Cryptographic Constructions

[BibT_eX]

[DOI]

Rosario Gennaro

Electron. Colloquium Comput. Complex., 2000

Interactive and probabilistic proof-checking.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2000

Approximating Satisfiable Satisfiability Problems.

[BibT_eX]

[DOI]

Algorithmica, 2000

Erratum: A Correction to "Parallel Approximation Algorithms by Positive Linear Programming".

[BibT_eX]

[DOI]

Algorithmica, 2000

A PCP characterization of NP with optimal amortized query complexity.

[BibT_eX]

[DOI]

Alex Samorodnitsky

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

On the efficiency of local decoding procedures for error-correcting codes.

[BibT_eX]

[DOI]

Jonathan Katz

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Extracting Randomness from Samplable Distributions.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

A Survey of Optimal PCP Characterizations of NP.

[BibT_eX]

[DOI]

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

Max NP-completeness Made Easy.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1999

Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1999

Construction of Extractors Using Pseudo-Random Generators (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Pseudorandom Generators Without the XOR Lemma (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Pseudorandom Generators without the XOR Lemma (Abstract).

[BibT_eX]

[DOI]

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

The Parallel Complexity of Positive Linear Programming.

[BibT_eX]

[DOI]

Fatos Xhafa

Parallel Process. Lett., 1998

A Case Study of De-randomization Methods for Combinatorial Approximation Algorithms.

[BibT_eX]

[DOI]

José D. P. Rolim

J. Comb. Optim., 1998

Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Probabilistically checkable proofs with low amortized query complexity

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

A tight characterization of NP with 3 query PCPs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Recycling Queries in PCPs and in Linearity Tests

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Recent Advances Towards Proving P = BPP.

[BibT_eX]

José D. P. Rolim

Bull. EATCS, 1998

Parallel Approximation Algorithms by Positive Linear Programming.

[BibT_eX]

[DOI]

Algorithmica, 1998

Recycling Queries in PCPs and in Linearity Tests (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming.

[BibT_eX]

[DOI]

Maria J. Serna

Fatos Xhafa

Proceedings of the STACS 98, 1998

1997

On the Efficiency of Polynomial Time Approximation Schemes.

[BibT_eX]

[DOI]

Marco Cesati

Inf. Process. Lett., 1997

Weak Random Sources, Hitting Sets, and BPP Simulations

[BibT_eX]

[DOI]

Alexander E. Andreev

José D. P. Rolim

Electron. Colloquium Comput. Complex., 1997

When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Approximating Satisfiable Satisfiability Problems (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1997

1996

On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1996

A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1996

Structure in Approximation Classes

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

Constraint satisfaction: The approximability of minimization problems.

[BibT_eX]

[DOI]

Sanjeev Khanna

Electron. Colloquium Comput. Complex., 1996

On the Approximability of the Multi-dimensional Euclidean TSP

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

Bisimilarity Problems Requiring Exponential Time.

[BibT_eX]

[DOI]

Michele Boreale

Proceedings of the Mathematical Foundations of Computer Science 1996, 1996

To Weight or Not to Weight: Where is the Question?

[BibT_eX]

Riccardo Silvestri

Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

Gadgets, Approximation, and Linear Programming (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Positive Linear Programming, Parallel Approximation and PCP's.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1996

Improved Non-approximability Results for Vertex Cover with Density Constraints.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995

On the Complexity of Bisimilarity for Value-Passing Processes (Extended Abstract).

[BibT_eX]

[DOI]

Michele Boreale

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995

Structure in Approximation Classes (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1994

Minimum Vertex Cover, Distributed Decision-Making, and Communication Complexity (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

On Approximation Scheme Preserving Reducability and Its Applications.

[BibT_eX]

[DOI]