Venkatesan Guruswami

IACR Cryptol. ePrint Arch., 2024

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

Geno-Weaving: Low-Complexity Capacity-Achieving DNA Storage.

[BibT_eX]

[DOI]

CoRR, 2024

Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates.

[BibT_eX]

[DOI]

Louis Golowich

CoRR, 2024

Tight bounds for stream decodable error-correcting codes.

[BibT_eX]

[DOI]

Meghal Gupta

Mihir Singhal

CoRR, 2024

Exponential Time Approximation for Coloring 3-Colorable Graphs.

[BibT_eX]

[DOI]

Rhea Jain

CoRR, 2024

Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett and Cheraghchi-Nakos's Nonadaptive Splitting with Explicit Scalars.

[BibT_eX]

[DOI]

Ryan Gabrys

CoRR, 2024

Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Isolate and then Identify: Rethinking Adaptive Group Testing.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2024

Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2024

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold.

[BibT_eX]

[DOI]

Jun-Ting Hsieh

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Decoding Quasi-Cyclic Quantum LDPC Codes.

[BibT_eX]

[DOI]

Louis Golowich

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Outlier Robust Multivariate Polynomial Regression.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Capacity-Achieving Gray Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Efficient Linear and Affine Codes for Correcting Insertions/Deletions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., June, 2023

Inapproximability of Matrix p → q Norms.

[BibT_eX]

[DOI]

SIAM J. Comput., February, 2023

Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2023

Baby PIH: Parameterized Inapproximability of Min CSP.

[BibT_eX]

[DOI]

Xuandi Ren

Electron. Colloquium Comput. Complex., 2023

Parameterized Inapproximability Hypothesis under ETH.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Quantum Locally Recoverable Codes.

[BibT_eX]

[DOI]

Louis Golowich

Electron. Colloquium Comput. Complex., 2023

AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding.

[BibT_eX]

[DOI]

CoRR, 2023

Improved rate-distance trade-offs for quantum codes with restricted connectivity.

[BibT_eX]

[DOI]

CoRR, 2023

Binary Error-Correcting Codes with Minimal Noiseless Feedback.

[BibT_eX]

[DOI]

Meghal Gupta

Rachel Yun Zhang

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

SDPs and Robust Satisfiability of Promise CSP.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett's Nonadaptive Splitting with Explicit Scalars.

[BibT_eX]

[DOI]

Ryan Gabrys

Proceedings of the IEEE International Symposium on Information Theory, 2023

How Many Matrices Should I Prepare To Polarize Channels Optimally Fast?

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2023

On expanding the toolkit of locality-based coded computation to the coordinates of inputs.

[BibT_eX]

[DOI]

Michael Rudow

K. V. Rashmi

Proceedings of the IEEE International Symposium on Information Theory, 2023

Hardness of Learning Boolean Functions from Label Proportions.

[BibT_eX]

[DOI]

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble.

[BibT_eX]

[DOI]

Shilun Li

Proceedings of the Approximation, 2023

2022

Arıkan Meets Shannon: Polar Codes With Near-Optimal Convergence to Channel Capacity.

[BibT_eX]

[DOI]

Min Ye

IEEE Trans. Inf. Theory, 2022

Threshold Rates for Properties of Random Codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2022

Bounds for List-Decoding and List-Recovery of Random Linear Codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2022

Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Beating Fredman-Komlós for perfect k-hashing.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2022

Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness.

[BibT_eX]

[DOI]

Xin Lyu

Xiuhan Wang

Electron. Colloquium Comput. Complex., 2022

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓp Norms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2022

Sparsity and 𝓁p-Restricted Isometry.

[BibT_eX]

[DOI]

CoRR, 2022

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random.

[BibT_eX]

[DOI]

Pravesh K. Kothari

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Punctured Low-Bias Codes Behave Like Random Linear Codes.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

ℓp-Spread and Restricted Isometry Properties of Sparse Random Matrices.

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number.

[BibT_eX]

[DOI]

Pravesh K. Kothari

Proceedings of the Approximation, 2022

Accelerating Polarization via Alphabet Extension.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2022

2021

Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

The zero-rate threshold for adversarial bit-deletions is less than 1/2.

[BibT_eX]

[DOI]

Xiaoyu He

Electron. Colloquium Comput. Complex., 2021

Improved Maximally Recoverable LRCs using Skew Polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Conditional Dichotomy of Boolean Ordered Promise CSPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

CNF Satisfiability in a Subspace and Related Problems.

[BibT_eX]

[DOI]

Vikraman Arvind

Electron. Colloquium Comput. Complex., 2021

Revisiting a Lower Bound on the Redundancy of Linear Batch Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Visible Rank and Codes with Locality.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

𝓁p-Spread Properties of Sparse Matrices.

[BibT_eX]

[DOI]

CoRR, 2021

Strongly refuting all semi-random Boolean CSPs.

[BibT_eX]

[DOI]

Jackson Abascal

Pravesh K. Kothari

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

A locality-based lens for coded computation.

[BibT_eX]

[DOI]

Michael Rudow

K. V. Rashmi

Proceedings of the IEEE International Symposium on Information Theory, 2021

Linear Programming Bounds for Almost-Balanced Binary Codes.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2021

Linear Shannon Capacity of Cayley Graphs.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2021

Sharp Threshold Rates for Random Codes.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

ϵ-MSR Codes: Contacting Fewer Code Blocks for Exact Repair.

[BibT_eX]

[DOI]

Sai Vikneshwar Mani Jayaraman

Satyanarayana V. Lokam

IEEE Trans. Inf. Theory, 2020

Coding Against Deletions in Oblivious and Online Models.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2020

Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields.

[BibT_eX]

[DOI]

Lingfei Jin

IEEE Trans. Inf. Theory, 2020

Maximally Recoverable LRCs: A Field Size Lower Bound and Constructions for Few Heavy Parities.

[BibT_eX]

[DOI]

Sergey Yekhanin

IEEE Trans. Inf. Theory, 2020

An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel.

[BibT_eX]

[DOI]

Marco Dalai

Jaikumar Radhakrishnan

IEEE Trans. Inf. Theory, 2020

The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Optimal rate list decoding over bounded alphabets using algebraic-geometric codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Pseudobinomiality of the Sticky Random Walk.

[BibT_eX]

[DOI]

Vinayak Kumar

Electron. Colloquium Comput. Complex., 2020

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

An Algorithmic Study of the Hypergraph Turán Problem.

[BibT_eX]

[DOI]

CoRR, 2020

A locality-based approach for coded computation.

[BibT_eX]

[DOI]

Michael Rudow

K. V. Rashmi

CoRR, 2020

Symmetric Polymorphisms and Efficient Decidability of Promise CSPs.

[BibT_eX]

[DOI]

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

Leakage-Resilient Secret Sharing in Non-Compartmentalized Models.

[BibT_eX]

[DOI]

Fuchun Lin

Reihaneh Safavi-Naini

Huaxiong Wang

Proceedings of the 1st Conference on Information-Theoretic Cryptography, 2020

d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

How Long Can Optimal Locally Repairable Codes Be?

[BibT_eX]

[DOI]

Chen Yuan

IEEE Trans. Inf. Theory, 2019

Polynomial Time Decodable Codes for the Binary Deletion Channel.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2019

$d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Rainbow coloring hardness via low sensitivity polymorphisms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity.

[BibT_eX]

[DOI]

Min Ye

Electron. Colloquium Comput. Complex., 2019

Revisiting Alphabet Reduction in Dinur's PCP.

[BibT_eX]

[DOI]

Jakub Oprsal

Electron. Colloquium Comput. Complex., 2019

Optimally Resilient Codes for List-Decoding from Insertions and Deletions.

[BibT_eX]

[DOI]

Bernhard Haeupler

Amirbehshad Shahrasbi

Electron. Colloquium Comput. Complex., 2019

CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Bridging between 0/1 and Linear Programming via Random Walks.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

An Exponential Lower Bound on the Sub-Packetization of MSR Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Non-Malleable Secret Sharing against Affine Tampering.

[BibT_eX]

[DOI]

Fuchun Lin

Reihaneh Safavi-Naini

Huaxiong Wang

CoRR, 2019

An Algorithmic Blend of LPs and Ring Equations for Promise CSPs.

[BibT_eX]

[DOI]

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

Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness.

[BibT_eX]

[DOI]

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

Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization.

[BibT_eX]

[DOI]

Haotian Jiang

Proceedings of the IEEE International Symposium on Information Theory, 2019

Algorithmic Polarization for Hidden Markov Models.

[BibT_eX]

[DOI]

Preetum Nakkiran

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Streaming Hardness of Unique Games.

[BibT_eX]

[DOI]

Runzhou Tao

Proceedings of the Approximation, 2019

2018

MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2018

Secret Sharing with Binary Shares.

[BibT_eX]

[DOI]

Fuchun Lin

Reihaneh Safavi-Naini

Huaxiong Wang

IACR Cryptol. ePrint Arch., 2018

Lossless dimension expanders via linearized polynomials and subspace designs.

[BibT_eX]

[DOI]

Nicolas Resch

Electron. Colloquium Comput. Complex., 2018

Beating Fredman-Komlós for perfect k-hashing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Combining LPs and Ring Equations via Structured Polymorphisms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

General Strong Polarization.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Approximating Operator Norms via Generalized Krivine Rounding.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Inapproximability of Matrix p→q Norms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231).

[BibT_eX]

[DOI]

Martin Grohe

Stanislav Zivný

Dagstuhl Reports, 2018

Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy.

[BibT_eX]

[DOI]

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

On the List-Decodability of Random Linear Rank-Metric Codes.

[BibT_eX]

[DOI]

Nicolas Resch

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

∊-MSR Codes: Contacting Fewer Code Blocks for Exact Repair.

[BibT_eX]

[DOI]

Sai Vikneshwar Mani Jayaraman

Satyanarayana V. Lokam

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

Polar Codes with Exponentially Small Error at Finite Block Length.

[BibT_eX]

[DOI]

Jaroslaw Blasiok

Proceedings of the Approximation, 2018

Explicit optimal-length locally repairable codes of distance 5.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual Allerton Conference on Communication, 2018

2017

Repairing Reed-Solomon Codes.

[BibT_eX]

[DOI]

Mary Wootters

IEEE Trans. Inf. Theory, 2017

Deletion Codes in the High-Noise and High-Rate Regimes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2017

Efficiently List-Decodable Punctured Reed-Muller Codes.

[BibT_eX]

[DOI]

Lingfei Jin

IEEE Trans. Inf. Theory, 2017

An Improved Bound on the Fraction of Correctable Deletions.

[BibT_eX]

[DOI]

Boris Bukh

IEEE Trans. Inf. Theory, 2017

Inapproximability of H-Transversal/Packing.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

Nearly Optimal NP-Hardness of Unique Coverage.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

(2+ε)-Sat Is NP-hard.

[BibT_eX]

[DOI]

Per Austrin

SIAM J. Comput., 2017

Subspace Designs based on Algebraic Function Fields.

[BibT_eX]

[DOI]

Chen Yuan

Electron. Colloquium Comput. Complex., 2017

Hardness of Rainbow Coloring Hypergraphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

On Maximally Recoverable Local Reconstruction Codes.

[BibT_eX]

[DOI]

Sergey Yekhanin

Electron. Colloquium Comput. Complex., 2017

A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

The Quest for Strong Inapproximability Results with Perfect Completeness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth.

[BibT_eX]

[DOI]

Ankit Singh Rawat

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

∊-MSR codes with small sub-packetization.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere.

[BibT_eX]

[DOI]

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

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph.

[BibT_eX]

[DOI]

Ameya Velingker

Santhoshini Velusamy

Proceedings of the Approximation, 2017

Efficiently Decodable Codes for the Binary Deletion Channel.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

Locality via Partially Lifted Codes.

[BibT_eX]

[DOI]

S. Luna Frank-Fischer

Mary Wootters

Proceedings of the Approximation, 2017

Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere.

[BibT_eX]

[DOI]

Vijay Bhattiprolu

Proceedings of the Approximation, 2017

2016

Decoding Reed-Solomon Codes.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Simple Proof of Hardness of Feedback Vertex Set.

[BibT_eX]

[DOI]

Theory Comput., 2016

Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2016

Optimal Rate Code Constructions for Computationally Simple Channels.

[BibT_eX]

[DOI]

Adam D. Smith

J. ACM, 2016

Tight bounds for communication assisted agreement distillation.

[BibT_eX]

[DOI]

Jaikumar Radhakrishnan

Electron. Colloquium Comput. Complex., 2016

New hardness results for graph and hypergraph colorings.

[BibT_eX]

[DOI]

Vijay V. S. P. Bhattiprolu

Electron. Colloquium Comput. Complex., 2016

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

New MDS codes with small sub-packetization and near-optimal repair bandwidth.

[BibT_eX]

[DOI]

Ankit Singh Rawat

CoRR, 2016

Codes correcting deletions in oblivious and random models.

[BibT_eX]

[DOI]

CoRR, 2016

Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey).

[BibT_eX]

[DOI]

Vijay V. S. P. Bhattiprolu

CoRR, 2016

Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy.

[BibT_eX]

[DOI]

CoRR, 2016

Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2016

Robust Fourier and Polynomial Curve Fitting.

[BibT_eX]

[DOI]

David Zuckerman

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Optimal rate algebraic list decoding using narrow ray class fields.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2015

Towards a Characterization of Approximation Resistance for Symmetric CSPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

An improved bound on the fraction of correctable deletions.

[BibT_eX]

[DOI]

Boris Bukh

Electron. Colloquium Comput. Complex., 2015

Efficient Low-Redundancy Codes for Correcting Multiple Deletions.

[BibT_eX]

[DOI]

Samuel Zbarsky

Electron. Colloquium Comput. Complex., 2015

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

Efficient list decoding of punctured Reed-Muller codes.

[BibT_eX]

[DOI]

Lingfei Jin

Vijay V. S. P. Bhattiprolu

CoRR, 2015

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

Combinatorial Limitations of Average-Radius List-Decoding.

[BibT_eX]

[DOI]

Srivatsan Narayanan

IEEE Trans. Inf. Theory, 2014

Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems.

[BibT_eX]

[DOI]

SIAM J. Optim., 2014

An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets.

[BibT_eX]

[DOI]

Ameya Velingker

Electron. Colloquium Comput. Complex., 2014

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Inapproximability of Feedback Vertex Set for Bounded Length Cycles.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Dimension Expanders via Rank Condensers.

[BibT_eX]

[DOI]

Michael A. Forbes

Electron. Colloquium Comput. Complex., 2014

Communication with Imperfectly Shared Randomness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

(2 + epsilon)-Sat Is NP-Hard.

[BibT_eX]

[DOI]

Per Austrin

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Evading Subspaces Over Large Fields and Explicit List-decodable Rank-metric Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes.

[BibT_eX]

[DOI]

Ameya Velingker

SIAM J. Comput., 2013

Hitting Sets for Low-Degree Polynomials with Optimal Density.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Polar Codes: Speed of polarization and polynomial gap to capacity.

[BibT_eX]

[DOI]

Patrick Xia

Electron. Colloquium Comput. Complex., 2013

Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Explicit rank-metric codes list-decodable with optimal redundancy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs.

[BibT_eX]

[DOI]

Sushant Sachdeva

Electron. Colloquium Comput. Complex., 2013

Superlinear lower bounds for multipass graph processing.

[BibT_eX]

[DOI]

Krzysztof Onak

Electron. Colloquium Comput. Complex., 2013

Complexity of approximating CSP with Balance / Hard Constraints.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Explicit Subspace Designs.

[BibT_eX]

[DOI]

Swastik Kopparty

Electron. Colloquium Comput. Complex., 2013

PCPs via low-degree long code and hardness for constrained hypergraph coloring.

[BibT_eX]

[DOI]

Irit Dinur

Electron. Colloquium Comput. Complex., 2013

Non-Malleable Coding Against Bit-wise and Split-State Tampering.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Capacity of Non-Malleable Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs.

[BibT_eX]

[DOI]

CoRR, 2013

CopyCatch: stopping group attacks by spotting lockstep behavior in social networks.

[BibT_eX]

[DOI]

Proceedings of the 22nd International World Wide Web Conference, 2013

Approximating Non-Uniform Sparsest Cut Via Generalized Spectra.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

2012

Agnostic Learning of Monomials by Halfspaces Is Hard.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Approximating Bounded Occurrence Ordering CSPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Linear-algebraic list decoding for variants of Reed-Solomon codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Faster SDP hierarchy solvers for local rounding algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Combinatorial limitations of a strong form of list decoding.

[BibT_eX]

[DOI]

Srivatsan Narayanan

Electron. Colloquium Comput. Complex., 2012

Optimal column-based low-rank matrix reconstruction.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph.

[BibT_eX]

[DOI]

Aditya Bhaskara

Aravindan Vijayaraghavan

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

List decoding subspace codes from insertions and deletions.

[BibT_eX]

[DOI]

Srivatsan Narayanan

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2011

Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

List Decoding Tensor Products and Interleaved Codes.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Special Section on the Fortieth Annual ACM Symposium On Theory Of Computing (STOC 2008).

[BibT_eX]

[DOI]

Shuchi Chawla

Cynthia Dwork

SIAM J. Comput., 2011

Hardness amplification within NP against deterministic algorithms.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Certifying Graph Expansion and Non-Uniform Sparsity via Generalized Spectra

[BibT_eX]

[DOI]

CoRR, 2011

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

[BibT_eX]

[DOI]

Aditya Bhaskara

Aravindan Vijayaraghavan

CoRR, 2011

The query complexity of estimating weighted averages.

[BibT_eX]

[DOI]

Acta Informatica, 2011

Finding Almost-Perfect Graph Bisections.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Linear-Algebraic List Decoding of Folded Reed-Solomon Codes.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Optimal Rate List Decoding via Derivative Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

A Lower Bound on List Size for List Decoding.

[BibT_eX]

[DOI]

Salil P. Vadhan

IEEE Trans. Inf. Theory, 2010

The existence of concatenated codes list-decodable up to the hamming bound.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2010

Locally Testable Codes Require Redundant Testers.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate.

[BibT_eX]

[DOI]

Adam D. Smith

Electron. Colloquium Comput. Complex., 2010

Bypassing UGC from some optimal geometric inapproximability results.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

On the List-Decodability of Random Linear Codes.

[BibT_eX]

[DOI]

Swastik Kopparty

Electron. Colloquium Comput. Complex., 2010

Almost Euclidean subspaces of l 1N VIA expander codes.

[BibT_eX]

[DOI]

Alexander A. Razborov

Comb., 2010

On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

SDP Gaps for 2-to-1 and Other Label-Cover Variants.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Hardness of Learning Halfspaces with Noise.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes.

[BibT_eX]

[DOI]

Christopher Umans

Salil P. Vadhan

J. ACM, 2009

Improved Inapproximability Results for Maximum k-Colorable Subgraph.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Error correction up to the information-theoretic limit.

[BibT_eX]

[DOI]

Commun. ACM, 2009

MaxMin allocation via degree lower-bounded arborescences.

[BibT_eX]

[DOI]

MohammadHossein Bateni

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

List Decoding of Binary Codes-A Brief Survey of Some Recent Results.

[BibT_eX]

[DOI]

Proceedings of the Coding and Cryptology, Second International Workshop, 2009

Every Permutation CSP of arity 3 is Approximation Resistant.

[BibT_eX]

[DOI]

Rajsekar Manokaran

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Expander codes over reals, Euclidean sections, and compressed sensing.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008

Decoding Reed-Solomon Codes.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2008

Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets.

[BibT_eX]

[DOI]

Anindya C. Patthak

Math. Comput., 2008

Concatenated codes can achieve list-decoding capacity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Soft decoding, dual BCH codes, and better list-decodable eps-biased codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Hardness Amplification via Space-Efficient Direct Products.

[BibT_eX]

[DOI]

Valentine Kabanets

Comput. Complex., 2008

Algorithms for Modular Counting of Roots of Multivariate Polynomials.

[BibT_eX]

[DOI]

Richard J. Lipton

Algorithmica, 2008

Almost Euclidean subspaces of lN1 via expander codes.

[BibT_eX]

[DOI]

Alexander A. Razborov

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction.

[BibT_eX]

[DOI]

Widad Machmouchi

Proceedings of the 2008 IEEE International Symposium on Information Theory, 2008

List Error-Correction with Optimal Information Rate (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the Information Theoretic Security, Third International Conference, 2008

Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph.

[BibT_eX]

[DOI]

Rajsekar Manokaran

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

Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the Approximation, 2008

2007

Guessing secrets efficiently via list decoding.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

Better Binary List-Decodable Codes via Multilevel Concatenation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Almost Euclidean subspaces of ℓ1N via expander codes.

[BibT_eX]

[DOI]

Alexander A. Razborov

Electron. Colloquium Comput. Complex., 2007

Deterministic Hardness Amplification via Local GMD Decoding.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword.

[BibT_eX]

[DOI]

Valentine Kabanets

Comput. Complex., 2007

A 3-query PCP over integers.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Hardness of routing with congestion in directed graphs.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

List Decoding and Pseudorandom Constructions.

[BibT_eX]

[DOI]

Proceedings of the Applied Algebra, 2007

2006

Correlation Clustering with a Fixed Number of Clusters.

[BibT_eX]

[DOI]

Ioannis Giotis

Theory Comput., 2006

Limits to List Decoding Reed-Solomon Codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2006

Algorithmic Results in List Decoding.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2006

Extractors and condensers from univariate polynomials.

[BibT_eX]

[DOI]

Christopher Umans

Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2006

Hardness of Low Congestion Routing in Directed Graphs.

[BibT_eX]

[DOI]

Kunal Talwar

Electron. Colloquium Comput. Complex., 2006

Iterative Decoding of Low-Density Parity Check Codes (A Survey).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Iterative Decoding of Low-Density Parity Check Codes.

[BibT_eX]

Bull. EATCS, 2006

List Decoding in Average-Case Complexity and Pseudorandomness.

[BibT_eX]

[DOI]

Proceedings of the 2006 IEEE Information Theory Workshop, 2006

On 2-Query Codeword Testing with Near-Perfect Completeness.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2005

Linear-time encodable/decodable codes with near-optimal rate.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2005

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Clustering with qualitative information.

[BibT_eX]

[DOI]

Anthony Wirth

J. Comput. Syst. Sci., 2005

Explicit Capacity-Achieving List-Decodable Codes

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Algebraic-geometric generalizations of the Parvaresh-Vardy codes

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Tolerant Locally Testable Codes

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

The complexity of the covering radius problem.

[BibT_eX]

[DOI]

Daniele Micciancio

Oded Regev

Comput. Complex., 2005

On profit-maximizing envy-free pricing.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Hardness of Max 3SAT with No Mixed Clauses.

[BibT_eX]

[DOI]

Subhash Khot

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

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

[BibT_eX]

[DOI]

Luca Trevisan

Proceedings of the Approximation, 2005

2004

Guest column: error-correcting codes and expander graphs.

[BibT_eX]

[DOI]

SIGACT News, 2004

Guest Editors' foreword.

[BibT_eX]

[DOI]

Edith Cohen

J. Comput. Syst. Sci., 2004

Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

[BibT_eX]

[DOI]

Alexander Vardy

Electron. Colloquium Comput. Complex., 2004

Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses.

[BibT_eX]

[DOI]

Algorithmica, 2004

Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Linear-Time List Decoding in Error-Free Settings: (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

The Complexity of the Covering Radius Problem on Lattices and Codes.

[BibT_eX]

[DOI]

Daniele Micciancio

Oded Regev

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition)

[BibT_eX]

[DOI]

Lecture Notes in Computer Science 3282, Springer, ISBN: 3-540-24051-9, 2004

2003

List decoding from erasures: bounds and code constructions.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2003

Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

Better Extractors for Better Codes?

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Linear time encodable and list decodable codes.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Unconditional proof of tightness of Johnson bound.

[BibT_eX]

[DOI]

Igor E. Shparlinski

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Embeddings and non-approximability of geometric problems.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

List Decoding with Side Information.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Combinatorial bounds for list decoding.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2002

Hardness of Approximate Hypergraph Coloring.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

Query Strategies for Priced Information.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Is Constraint Satisfaction Over Two Variables Always Easy?

[BibT_eX]

[DOI]

Lars Engebretsen

Electron. Colloquium Comput. Complex., 2002

Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon)

[BibT_eX]

[DOI]

Irit Dinur

Subhash Khot

Electron. Colloquium Comput. Complex., 2002

Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Limits to list decodability of linear codes.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Decoding Concatenated Codes using Soft Information.

[BibT_eX]

[DOI]

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

2001

List decoding of error correcting codes.

[BibT_eX]

[DOI]

PhD thesis, 2001

On representations of algebraic-geometry codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2001

Constructions of Codes from Number Fields

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

The Kr-Packing Problem.

[BibT_eX]

[DOI]

Computing, 2001

Expander-Based Constructions of Efficiently Decodable Codes.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

On the Hardness of 4-coloring a 3-colorable Graph

[BibT_eX]

[DOI]

Sanjeev Khanna

Electron. Colloquium Comput. Complex., 2000

Algorithmic aspects of clique-transversal and clique-independent sets.

[BibT_eX]

[DOI]

C. Pandu Rangan

Discret. Appl. Math., 2000

List decoding algorithms for certain concatenated codes.

[BibT_eX]

[DOI]

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

Query strategies for priced information (extended abstract).

[BibT_eX]

[DOI]

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

"Soft-decision" Decoding of Chinese Remainder Codes.

[BibT_eX]

[DOI]

Amit Sahai

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

Combinatorial feature selection problems.

[BibT_eX]

[DOI]

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

On Representations of Algebraic-Geometric Codes for List Decoding.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2000

1999

Improved decoding of Reed-Solomon and algebraic-geometry codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1999

The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

Enumerative aspects of certain subclasses of perfect graphs.

[BibT_eX]

[DOI]

Discret. Math., 1999

Maximum Cut on Line and Total Graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1999

The 2-Catalog Segmentation Problem.

[BibT_eX]

[DOI]

Yevgeniy Dodis

Sanjeev Khanna

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Multiclass Learning, Boosting, and Error-Correcting Codes.

[BibT_eX]

[DOI]

Amit Sahai

Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

1998

A Natural Family of Optimization Problems with Arbitrarily Small Approximation Thresholds.

[BibT_eX]

[DOI]

C. Pandu Rangan

Inf. Process. Lett., 1998

Improved decoding of Reed-Solomon and algebraic-geometric codes.

[BibT_eX]

[DOI]